A Turing Machine in Minecraft

This is an English translation of my original article on Habr, originally published in Russian.

A Turing machine is one of the fundamental models in computer science. I've been playing Minecraft for more than 12 years and have built all kinds of mechanisms in the game. After years of university study and working in the industry, I had an idea: combine my hobby with fundamental theory, build a Turing machine using Minecraft's mechanics, and share the result.

A Turing machine has three basic components:

• Tape: a sequence of consecutive cells—infinite in the theoretical model.
• Head: a read/write device positioned over the current tape cell.
• Transition table: the machine's program, expressed as a formal set of instructions.

Detailed explanations of Turing machine theory are easy to find, so I'll focus on the implementation.

Redstone: the basis of the simulation

Minecraft has a built-in system for simulating electrical signals: redstone. Let's go over its basic building blocks.

Signals and power levels

A redstone signal has 16 power levels, from 0 (no signal) to 15 (maximum strength). Redstone dust carries a signal for up to 15 blocks, losing one power level per block.

Wiring. Redstone dust is the main signal conductor. It automatically connects to neighboring dust, blocks, and components to form circuits.

Key components

• Redstone torch: an inverting source. It is on by default and turns off when the block it is attached to receives power. It is effectively a NOT gate.
• Lever: when switched on, it fully powers the block it is attached to, providing a steady signal.
• Button: similar to a lever, but produces a pulse of fixed duration.
• Repeater: restores a signal to full strength, passes it in only one direction, and introduces a delay of 1–4 redstone ticks. It is essential for long circuits and controlling signal direction.
• Comparator: compares two signals. In comparison mode, it passes the main input only when it is greater than or equal to the side input. In subtraction mode, it subtracts the side input from the main input. Comparators are useful for more complex logic.

Logic gates

Torches, repeaters, and dust can be combined into all the basic logic gates:

• NOT: a torch at the end of a wire inverts the signal.
• AND: two repeaters feed torches whose outputs converge on a single block with an output torch.
• OR: two wires merge into one; the output is active if at least one input is active.
• NAND / NOR: combinations of the gates above.

These primitives form the larger parts of the machine: tape memory, head logic, and the state table.

Alphabet

For convenience, I chose an alphabet of four symbols. This lets me represent 0 and 1, a special blank symbol indicating an empty cell, and one spare value.

Implementation

Memory cell

The memory cell stores data on the tape. It contains four bits and can hold values from 0 to 15. Once activated (Figure 1), it continuously outputs the stored signal—in this example, 0101.

The input section on the left has a reset button beneath the first sign. Four bits are more than this implementation needs; I chose that capacity with future extensions in mind.

Figure 1. Memory cell

Shift register

To select one of several memory cells, the machine needs a shift register. It has a row of lamps: the lit lamp indicates the cell the head points to.

On the right, below the signs in Figure 2, there are three buttons:

1. Move the head one cell to the left.
2. Move the head one cell to the right.
3. Reset the shift register to its initial position.

In the initial position, the leftmost lamp is on.

An optional lamp stands separately on the left. It lights up whenever the shift register finishes a move. This completion signal can be used to minimize delays in the main execution loop while ensuring that each shift has finished. In effect, this mechanism implements a bit-shift operation.

Figure 2. Shift register

Program cell

A program cell is the basic storage unit of the transition table. It holds ten bits of information:

• The first four bits specify the value to write to the tape cell currently selected by the head.
• The next two bits specify the head movement: 10 means left, and 01 means right. The cell shown in Figure 3 is configured to move left.
• The final four bits specify the next state, entered after the head moves. Again, four bits are more than needed here, but leave room for future extensions.

When a program cell is executed, it first writes a value to the tape, then moves the head, and finally switches to the selected state.

Figure 3. Program cell

Binary-to-decimal decoder

The program is encoded in binary, so the machine needs a way to select physical components using binary values. This decoder is optional, but greatly simplifies both the logic and the construction of the Turing machine.

In Figure 4, a binary number is supplied on the right—in this case, 10. The output on the left indicates the corresponding decimal value: 2.

Figure 4. Binary-to-decimal decoder

Execution cycle

The machine starts with its execution loop. The loop uses fixed delays between operations on its components. For example: read a cell, wait two seconds; write to a cell, wait two seconds; and so on.

The components are not wired into a completion-signaling system. If the loop sends a command to move the head right, it does not receive a signal telling it exactly when that operation finishes. There is no particular technical obstacle to adding this; I used fixed delays to get a working result sooner.

The overall sequence is:

1. Start the machine.
2. Read the symbol in the current memory cell.
3. Look up the transition using the current state and the symbol read from the tape.
4. Write the value from the transition table to the current cell.
5. Move the head.
6. Switch to the next state.
7. If the state is empty, send a signal to stop the execution loop. Otherwise, return to step 2.

After assembling all the components and connecting the necessary lines, we have a Turing machine in Minecraft.

Figure 5. The Turing machine in Minecraft

Viewed from above, the mechanism's individual components are easier to examine in action.

Figure 6. Top view of the Turing machine

The numbered components are:

1. The encoded program: four states, including one halting state, and four alphabet symbols, including the blank symbol, ε. The build contains 20 basic program cells.
2. The tape: eight memory cells, for a total of 32 bits of tape memory.
3. The shift register.
4. The execution loop.
5. The binary-to-decimal decoders.

The orange wire running from component 1 to component 4 carries the halt signal. Entering the halting state triggers this signal and stops the program's execution loop.

Figure 7. Main components, viewed from above

Additional views

Figure 8. Close-up view

Figure 9. View of the execution loop

Conclusion

The result is an interesting, fully functional mechanism implementing a particular instance of a Turing machine. You can watch it in action on YouTube. The example program increments a number entered on the tape beforehand.

Play Minecraft and have fun!

Original article: A Turing Machine in Minecraft — Habr (in Russian).