Using your Head is Permitted

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:

9
1012R
2013R
3014R
4015R
5014L
4113L
3112L
2111L
1110L

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: