3D chess is Turing-complete

As promised, here is the remainder of the proof of the Turing-completeness of three-dimensional chess. In the first part, we introduced the rules; in the second part, we built structures to function as logic gates and wires.

Counter machines

Instead of a Turing machine, I shall describe how to implement an alternative (equivalently universal) model, known as a counter machine. This is a finite state machine connected to a finite number (three is usual, but two is also sufficient) of registers, each of which can store a natural number. The finite state machine can send signals to increment and decrement the value of the register, and to test whether the register contains 0.

A more comprehensive description of a Minsky Register Machine (MRM) is included on Paul Chapman’s website, where he has built an implementation in Conway’s Game of Life. He uses sliding-block memory, developed by Dean Hickerson, where the position of a block represents an unbounded natural number. I have to admit that my design for a MRM in three-dimensional chess is directly inspired by Chapman’s implementation.

Sliding-king memory

The storage of positive integers uses a similar principle. The natural number is stored in the vertical position of a black king. Being able to increment and decrement the king with only finite support is non-trivial, and almost certainly the most difficult implementational detail. The key idea is to confine the black king to a helix, like so:

Then, forcing the king to move anticlockwise corresponds to incrementing the counter, and forcing it to move clockwise corresponds to decrementing the counter. To control the horizontal components of the position of the black king, we have an array of rook cages below, threatening upwards, and a single white king directly below the black king, protecting it from the rooks. Whenever the white king moves, the black king must also move to remain directly above it.

The other detail is to ensure that the king remains on the helix. The helix is contained in the union of four vertical planes. For each of these planes, we need to ensure that the z-coordinate of the king is restricted to a particular modulo-4 residue. Let’s consider one of these planes:

The white rooks are responsible for restricting the motion of the black king. Each rook is confined to a vertical column (shown in red); I’ll explain later how this is accomplished. The black knight is confined to two columns in the yz-plane, which ensures that the only positions on this xz-plane that it can occupy are those shown in light blue. The knight has the ability, therefore, to protect the king, provided he occupies a particular modulo-4 residue.

In other words, the black king can only occupy the squares highlighted in green. By including four copies of this mechanism, each screw-rotated by pi/2 and translated vertically upwards by one unit, we can restrict the black king to a helix.

Restricting the motion of rooks and knights

This mechanism would operate as the basis for a functioning sliding-king memory, assuming we can restrict the motion of the white rooks and black knights as described. Since this detail is quite difficult, I’ll explain precisely how this is accomplished. We’ll start with the white rooks. It’s easiest to explain this with a diagram:

The white rook (light green cube in the diagram) is pinned by the black rook immediately below it. The white king cannot move from its vertical column, lest it would be threatened by the eight surrounding black rooks. A fortress of pawns protect the white king from any attacks by rogue rooks; the king and pawns can move upwards to extend the reach of the rook.

The nine black rooks should actually be virtual rooks, emulated by a rook cage (nonplanar hexagon of mutually pinning rooks) as described in the previous article.

It is more difficult to control the black knights, since we need to restrict them to two vertical columns as opposed to just one. Equivalently, this reduces to preventing the black knights from landing on any of the sixteen columns shown in red in this horizontal cross-section:

To accomplish this, we have white rooks positioned directly below these columns, able to kill the knight if it enters one of them. We also have a black rook immediately below the white rook, able to destroy the white rook as soon as it moves (so as to prevent the rook from escaping) but not beforehand (as that would enable a defending white pawn to capture the black rook, resulting in a discovered checkmate). Using extra circuitry, it’s possible to ensure that checkmate occurs unless the black rook returns to its original position on the following move.

Completing the sliding-king memory

So far, I have described how the increment and decrement operations are carried out. It is also necessary to be able to test whether the black king is in a particular position (called the zero position). When in the zero position, the black king prevents a white king from passing through squares adjacent to the zero position, so the white king cannot generate a NZ (non-zero) signal. However, the black king also blocks a horizontal line of attack from a nearby black rook, so the white king can pass through a different passage, generating a Z (zero) signal.

Together with the fixed circuitry from the previous article (diodes and transistors), we can build a Turing-complete counter machine, proving that three-dimensional chess is itself Turing-complete.

Unsolved problems

There are still some unsolved problems:

• On each turn, a player has a potentially infinite number of moves (consider a single rook, for example). In theory, it may be possible to prove something stronger than Turing-completeness, namely that every statement in first-order Peano arithmetic can be encoded as a configuration. It seems as though this should be the case, although proving it will be tricky. This idea of infinitely many choices was necessary in the construction of positions where one player can force a mate, but not in any finite number of moves.
• Does three-dimensional chess retain Turing completeness when restricted to a smaller subset of pieces? In this proof, I required four distinct pieces, namely kings, rooks, knights and pawns.
• Is two-dimensional chess Turing-complete?

I believe that the answers to all of these questions are ‘yes’, but they are probably more difficult than this proof that three-dimensional chess is Turing-complete.