Chma

Chma is a family of problems which are all uncomputable since they can evaluate an EXPTIME-complete problem (such as evaluating a chess position) in polynomial time. The name comes from a shortening of "Chessmaster" due to the fact that the original problem was uncomputable specifically because it did that exact thing.

Chma1

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

It operates on a countably infinite tape of cells which can hold uncountably infinite values. The cells range from negative infinity to infinity, though if someone wants to try implementing the language, they can have the tape range from -30000 to 30000 and the cells be whatever float-type value seems reasonable. (The size of the tape and the values in the cells are not supposed to be the reason it's uncomputable.)

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

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 0, move the instruction pointer past the next ]
]	If the code pointer is not pointing at 0, move the instruction pointer back to the last [
!(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. Otherwise, it is not a valid implementation.

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