## 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:

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