Complexity class of chess when simulated by a Turing machine Suppose we simulate the game of chess with a Turing machine $M$ as follows:
The semi-infinite input tape of $M$ contains a sequence of symbols beginning in the first cell of the tape. Each symbol prescribes a possible chess move, i.e., an ordered pair of board positions, e.g., (a3, d5), indicating that the piece in the first position is to be moved to the second position. Thus, there are 64 x 64 such symbols. Note that not all moves would be valid or possible to carry out. Also, there is no explicit indication that there are two players making alternate moves.
Starting with the first cell of the input tape the machine $M$ reads the current symbol and does one of the following:
(1) If the move is possible to carry out, yet not a winning move, $M$ changes its internal state to one designating the new board configuration and any historical information it needs to record about the game (for castling, say) and moves to the next input symbol in the sequence.
(2) If the move is possible to carry out and it is a checkmate, $M$ halts (in "Win" state.)
(3) If the move is possible to carry out and it is a stalemate, $M$ halts  (in "Draw" state.)
(4) If the move is invalid or impossible to carry out, $M$ halts (in "Invalid" state.)
Which complexity class does $M$ belong to?
 A: First, it's not really necessary to include a bunch of stuff about explicit representation on a Turing machine's tape here.  Let me restate the question:

Given a sequence of chess moves which may or may not be valid, determine whether they describe a win for white, a win for black, a tie, or an illegal sequence of moves.

Now chess has a few obscure rules that keep the game from going into an infinite loop.  Let's ignore those for now.
Checking whether a given move is legal can always be done in constant time.  For most moves the only information involved is the current state of the board.  For castling and en passant we need to consult a fixed amount of additional state.
Consequently, the naive algorithm that just goes through the moves one by one and keeps an internal representation of the board is O(n).
Conversely, any algorithm to solve this problem must be O(n) since in the worst case you have to actually read every move in the list to determine the outcome. (Proof: take a valid game of any length and change any of the moves to an invalid one.  Any algorthm which doesn't check that move will not be able to determine an invalid move was made.)
Now let's add back in the 50 move rule or whatever.  These kind of rules put an upper bound on the length of the game.  This makes the problem O(1) because you only have to check the first, say, 10k moves, and then you can stop and declare the game a tie.
