The Logic Mill Specs

The Logic Mill is what less than 100 years later would be called the Turing machine. It has one tape and one head. It accepts the transition rules in the following format:

current_state current_symbol new_state write_symbol move_direction
current_state2 current_symbol2 new_state2 write_symbol2 move_direction
current_state3 current_symbol3 new_state3 write_symbol3 move_direction

• The Mill starts on the cell before the first non-blank cell of the input tape and is in the state INIT.
• The Mill halts when it's in the state HALT.
• Direction must be L or R for left or right respectively.
• _ is a blank symbol.

Limitations

• The tape length is limited to 2^20 cells (1 048 576 cells).
• The number of states is limited to 2^16 (65 536 states).
• State might be any string of up to 32 chars.

Example

Let's take unary number increment as an example. The number is represented as a sequence of |. For example, 4 is represented as |||| on the tape. The transition rules for increment would be:

INIT _ FIND _ R
FIND 1 FIND 1 R
FIND _ HALT 1 R

Below is the step-by-step execution of the Mill:

The Mill halts after 6 steps and the result is |||||, which represents the number 5.

Other Resources

• logic_mill.py — the source code of the Logic Mill I use in this project.
• TMSim — interactive simulator
• Turing Machine Simulator — uses a bit different transition rules format