Turing Machine on redstone Minecraft

Building a Turing Machine with Redstone in Minecraft

A Turing machine consists of an infinite tape divided into cells, a read/write head, and a transition table that acts as its program. In Minecraft, these components are simulated using Redstone—a signal transmission system with 16 power levels (0 to 15). Redstone dust carries a signal up to 15 blocks, dropping one strength level per block traveled.

Key Redstone components:

• Torch: Inverts the signal (NOT gate).
• Lever: Provides a stable, constant power source.
• Button: Generates a pulse of fixed duration.
• Repeater: Boosts signal strength, enforces one-way flow, and adds a 1–4 tick delay.
• Comparator: Compares or subtracts signal strengths.

These parts combine to form logic gates: NOT (torch), AND (two repeaters feeding into a torch), OR (converging wires), and NAND/NOR (various combinations). The machine uses a 4-symbol alphabet: 0, 1, empty (ε), and a reserved state.

Tape Memory Cell

Each cell stores 4 bits (values 0–15) and continuously outputs its signal once activated. For example, a cell might hold 0101. A button on the left resets the cell. The extra bits provide headroom for future expansions.

The full tape consists of 8 such cells, giving a total of 32 bits of storage.

Head Shift Register

This register tracks the read/write head’s position on the tape. A lit lamp indicates the current active cell. Buttons on the right control movement: left, right, and reset (which returns the head to the leftmost lamp). An optional lamp on the far left signals when a shift is complete, helping to minimize timing delays in the execution loop.

The register handles bit-shifting operations to move the head across the tape.

Program Cell

Each program cell holds 10 bits of instruction data:

• 4 bits for the value to write.
• 2 bits for the head offset (10 = move left, 01 = move right).
• 4 bits for the next machine state.

Operations follow a strict sequence: write → shift → state transition. The full program uses 20 cells, covering 4 states × 4 symbols (including ε and the halting state).

Binary-to-Decimal Converter

This module translates binary addresses into decimal format to correctly target tape cells. Input enters from the right (for example, binary 10 outputs as decimal 2 on the left). This simplifies memory addressing.

Execution Cycle

Fixed timing delays (2 seconds per operation) keep everything synchronized without needing explicit completion signals:

• Read the symbol from the current tape cell.
• Look up the transition rule based on the current state and symbol.
• Write the new value from the transition table.
• Shift the head left or right.
• Update to the next machine state.
• If the halting state is reached, stop; otherwise, repeat the cycle.

An orange wire runs from the program module to the execution loop to transmit the halt signal.

Overall Architecture

The complete build integrates:

• 20 program instruction cells.
• 8 tape memory cells.
• The head shift register.
• The synchronized execution cycle.
• Binary-to-decimal address converters.

As a practical demonstration, the machine can successfully increment a number stored on the tape.

Key Takeaways

• Redstone accurately simulates Turing machine logic using standard gates and 0–15 signal strengths.
• 4-bit memory cells include built-in redundancy for easier scaling.
• Fixed timing delays streamline the execution loop by eliminating the need for feedback signals.
• A 4-symbol alphabet and 4 internal states yield 20 possible transitions.
• The build is fully operational for specific use cases, such as binary incrementation.

— Editorial Team