Chma

Chma is a family of programming languages which were intended to be uncomputable since they could evaluate an EXPTIME-complete problem (such as evaluating a chess position) in polynomial time. The name came from a shortening of "Chessmaster" due to the fact that the original language specifically did that exact thing.

That said, these languages are only uncomputable in the literal, physical sense, not in the strict computational sense, since anything they can do can theoretically be done on a Turing machine, just not in polynomial time. Even though all implementations of these languages on any rationally constructed machine will fail to meet the specifications of the language, this is already normal for all Turing-complete languages on real physical machines since humans don't have infinite storage at their disposal.

Chma1

Chma1 is a simple language which directly and crudely fulfills the goal of the project.

It operates on a left-bounded, countably infinite tape of cells which can hold uncountably infinite values. If someone wants to try implementing the language, they can have the cells range from -30000 to 30000 and the cells be whatever float-type value seems reasonable.

The code pointer starts on the leftmost cell, which is considered cell 0. If someone wants to try implementing the language, they can have there be 30000 cells total.

Values entered have to consist entirely of digits, except for an optional minus sign in front and a single decimal point somewhere in the value to separate the decimal and non-decimal digits.

There is a code pointer and an instruction pointer.

Commands

Command	Explanation
+(c, v)	Adds the value v to the tape position c and moves the code pointer there
[	If the code pointer is pointing at a cell with a value between -0.5 and 0.5 exclusive, move the instruction pointer past the corresponding ]
]	If the code pointer is not pointing at a cell with a value between -0.5 and 0.5 exclusive, move the instruction pointer back to the corresponding [
!(w1, w2, b1, b2, s)	Given an s x s chessboard with two opponents, assume the cells where the code from cells wp1 to wp2 inclusive consists of piece type alternating with piece positions for the player who will go next, and the code from cells bp1 to bp2 inclusive consists of piece type alternating with piece positions for the player who has just moved, evaluate the position in polynomial time and put it in the current code pointer

Piece Explanation

Description	Elaboration
Piece Value	0 is pawn, 1 is knight, 2 is bishop, 3 is rook, 4 is queen, 5 is king; non-integer values are rounded down and then modulo 6 is taken
Piece Position	Value with a rounded-down value corresponding to a board space starting from the white square on White's right, going left until it hits the edge, then s+1 being the rightmost black square in the next row

The implementation must be able to do all of the above commands in polynomial time, even though this is mathematically impossible. Otherwise, it is not a valid implementation.

Any other errors caused by the ! command are implementation-dependent.

Computational Class

Chma1 is Turing-complete because it can change the stored memory arbitrarily, store it without mutating it, and loop arbitrarily.

Here is a translation of the Turing-complete BF commands, assuming the current location is #.

BF Translation

BF Command	Chma1 Command
>	+(#+1, 0)
<	+(#-1, 0)
+	+(#, 1)
-	+(#, -1)
[	[
]	]

I suppose you could call this language derivative.