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. The Mill requires a set of transition rules in the following format (one rule is one line): 

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).

The Mill knows nothing beyond its current state, the current symbol and the set of rules — any actions taken is decided by the rule matching that combination. There cannot be two rules for the same combination; if there were, the Mill would not be able to choose which one to apply! Also, the order of the rules does not matter, as the Mill jumps to whatever line has the current state/symbol combination.

Other rules:

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 to increment by 1 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 with the matching rule for each step:

Step Current tape Current State and Symbol New State and Symbol Move direction New tape
1 _||||_ INIT | FIND | (no symbol change) Right _||||_
2 _||||_ FIND | FIND | (no symbol change) Right _||||_
3 _||||_ FIND | FIND | (no symbol change) Right _||||_
4 _||||_ FIND | FIND | (no symbol change) Right _||||_
5 _||||_ FIND _ HALT | Right _|||||_

The Mill halts after 5 steps with the tape reading |||||, which represents the number 5 in unary. Success!

Solution optimization (advanced topic)

This section explains how to optimize your solutions. It is not required to solve quests, but it may help you understand how to create more efficient solutions.

Huge thanks to Xyzz for writing this explanation and parts of the tutorial!

The Mill required 3 rules to add 1 to 4 this way: 

INIT | FIND | R
FIND | FIND | R
FIND _ HALT _ R

Notice that the second rule was repeated until the end was reached, and then the third rule added the new |.

These 3 rules can actually add 1 to any unary number; if the task had been to add 1 to 5 it would just execute the second rule one more time. If the task had been to add 1 to 1, the same rules would still work, but rule#2 would be executed a total of 0 times.

Is this the only way to solve this task? No! To begin with, rule#1 and rule#2 are very similar and can actually be replaced with a single rule: 

INIT | INIT	| R	 // step to the right if symbol is |
INIT _ HALT	| R  // add | and halt if cell is empty

Now the first rule is repeated instead, until the end of the number is reached. The same result as before, but using only 2 rules!

Are there any more ways to add 1 to a number? Yes again! Below is an alternative 2-rule solution where INIT steps to the left instead:

Step Current tape Current State and Symbol New State and Symbol Move direction New tape
1 _||||_ INIT | INIT | (no symbol change) Left _||||_
2 _||||_ INIT _ HALT | Left |||||_

With this change the Mill still requires 2 rules, but it can now add 1 to any unary number in just 2 steps!

These principles can be applied to any task; at first you seek a set of rules that is able to solve the quest at all, but once you succeed you can try to find ways to optimize your solution for solving the quest in as few steps as possible or using as few rules as possible!

Visualization

Here is a video of the Mill running the unary number increment example (the original 5-step version):

You can also see the visualization in this interactive simulator.

Limitations

Other Resources

Next quest: Unary Addition →