Here’s a Turing machine example with a link to run it on a Turing Tumble simulator. A Turing machine is a model of a computer that reads and writes symbols on an infinite tape using a set of states. This version uses a finite four-cell tape just large enough for the example. Going past the tape boundaries will stop the machine with interceptors. Since it does not have an infinite tape this is not a formal Turing machine and does not prove Turing completeness.
This is the state table for the example 2-state, 2-symbol busy beaver Turing machine. Given the current state (A or B) and current tape symbol (0 or 1) it executes the corresponding three-character instruction in the table:
- write a new symbol (0 or 1),
- move the tape head (Left or Right) and
- set the next state (A, B or Halt).
The top part of the machine has four tape cells and the bottom part has two state registers. The distributor at the top of each tape cell and state register directs each serial 0 or 1 input ball to one of four pairs of paths in a repeating cycle of four balls. This allows any tape cell and any state to be connected for a four-ball cycle of synchronized processing with two-way data transfer by sending a 0 or 1 ball.
Executing each Turing machine state table instruction needs only three balls so the first two balls do the same thing and the first ball’s results are unused. The fourth ball completes the cycle and uses gear chains to select the next tape cell and state.
The machine can be reprogrammed to run a different Turing machine by changing the indicated ramps and gear bits at the bottom that define the state table. Each state register gets state table values from its left or right side if the saved tape symbol is 0 or 1 respectively. The design can be extended to run larger Turing machines by adding more gear chains, tape cells and state registers.
This busy beaver machine starts in state A at the third tape cell with a tape of all 0 symbols and moves back and forth writing 1s until it halts at the lower right Halt interceptor. It executes six four-ball steps using 24 balls and writes four 1s on the tape.
Here’s an image of the machine and a simulator link to run it. Start with either a blue or red ball.
