Tutorial — How to use the Logic Mill

The Logic Mill is the engine behind every quest in this world. It is a mechanical interpreter of symbolic logic—a device that reads, writes, and moves with unerring precision, according to the rules you define. To solve the problems that lie ahead, you must learn how the Mill operates, what it expects, and how it halts. This tutorial will teach you the essentials, so you can harness its power to solve puzzles, prove your wit, and uncover deeper mysteries.

The Logic Mill is what less than 100 years later would be called the Turing machine. It reads symbols on a tape, follows simple rules, and manipulates the tape step-by-step to solve a problem. It works by moving a read/write „head“ over a tape of symbols, changing one symbol at a time based on a set of transition rules. It accepts the transition rules in the following format:

currentState1 currentSymbol1 newState1 newSymbol1 moveDirection
currentState2 currentSymbol2 newState2 newSymbol2 moveDirection
currentState3 currentSymbol3 newState3 newSymbol3 moveDirection
...

Each transition rule has 5 parts:

1. currentState — The machine’s current state.
2. currentSymbol — The symbol under the head.
3. newState — The new state to switch to.
4. newSymbol — The symbol to write on the tape.
5. moveDirection — Move the head to the left (L) or right (R).

Other rules:

• The Mill starts on 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
• Each cell can contain only one symbol.
• A cell without a symbol is a blank cell and is represented by _
• You might comment your code by using // (see the example below)

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  // We start on the 1st non-blank cell and transition to FIND state
FIND | FIND | R  // We move right...
FIND _ HALT | R  // ...until we find a blank cell, which we change to | and halt

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

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

Visualization

Here is a video of the Mill running the unary number increment example:

You can also see the visualization in this interactive simulator.

Limitations

• The tape length is limited to 2^20 cells (1 048 576 cells).
• The number of states is limited to 2^10 (1024 states).
• State might be any string of up to 32 chars.
• The list of the transition rules is limited to 710 000 characters.
• The Mill has one tape and one head.

Other Resources

• logic_mill.py — the source code of the Logic Mill I use in this project.
• Turing Machine Simulator — interactive simulator that supports Logic Mill's transition rules format (thanks @avogadro007 for creating it!)
• TMSim — another interactive simulator (uses a bit different transition rules format).
• Turing Machine Simulator #2 — yet another interactive simulator (uses a different transition rules format).