Using your Head is Permitted

July 2012 riddle

UPDATE (1 July): To make the question more self-contained, I added a short description of what "Turing machine" means, at least in the present context.

To celebrate Alan Turing's 100'th birthday, this month Using your Head is Permitted is doing something special. This month, instead of a riddle we are having a contest.

Consider the set of all halting Turing machines with 5 states, which we number 1-5, plus a halting state which we denote 0, working on a bidirectionally infinite tape with two symbols, 0 and 1, where 0 is also the "blank" symbol. I stress that these are halting Turing machines. Non-halting Turing machines are not admitted to the set.

The contest is about finding a machine among this set that halts after the largest number of steps, when starting from a blank tape. Solvers will be listed by decreasing order of the number of steps their machines make before halting. Submission dates will be used only for tie breaking.

Obviously, if you have prior familiarity with this problem, please do not send your solution, and obviously do not send any non-original solutions.

To participate, please send in your machine's description as a text file, with the following format. On the first line, write the number of steps your machine makes before halting. If it is incorrect, your solution will be disqualified. Each line other than the first will denote a single cell in the machine's state-machine. It will be comprised of 5 characters, with no spacing, where the characters should be interpreted as follows:

If the state is [first character] and the symbol currently read is [second character], write [third character], move to state [fourth character] and move the tape's reading head one step in direction [fifth character].

The fifth character should be either R for "right" or L for "left". All other characters are digits. The initial state of the machine is state 1. If the second and third digits are the same, this indicates that the tape's contents has not changed.

For example, the following is a valid entry:


The order of the lines is insignificant (except for the first), and it's OK for a symbol table entry to be missing. A missing row is interpreted as a "halt" instruction in the state machine. In the example, the "51" line is missing.

Reminder of what we mean by a "Turing machine": consider an infinite bidirectional "tape", by which we mean an array indexed by the integers from negative infinity to positive infinity, which can store in each cell a bit. It is initialized by all zeros. The Turing machine has a "reading head", which is a pointer to this array, and is initialized to the zero position. The Turing machine also has an internal state. At each execution step, the machine reads the bit from the tape position indicated by the reading head, and then writes a new bit to the same position, advances the reading head one step to the left or right (effectively incrementing or decrementing the pointer), and moves to a new state. The heart of the Turing machine (which differentiates Turing machines from one another) is a state machine, known as the "finite control", which is a table listing for each combination of present state and read bit which new bit to write, which state to move to, and whether to move the reading head left or right. It is this table solvers are asked to provide for their machines. In the present context, the states are numbered 0-5, where 1 is the initial state of the machine and 0 is a special state that indicates program termination (known as the "halting" state).

Top solvers:

Jin Ruizhang & Zilin Jiang (41710) (13 July 18:49)
Daniel Bitin (41710) (30 July 06:42)

Elegant and original solutions can be submitted to the puzzlemaster at Names of solvers will be posted on this page. Notify if you don't want your name to be mentioned.

The solution will be published at the end of the month.


To solution

Back to main page