Turing machine

Turing machines are a model of computation first introduced by Alan Turing in 1936. As many similar formulations are equivalent in computational strength, the exact details of the formalism vary between authors. In the Busy Beaver space, the following conventions has been adopted:

• The machines use a single tape — a bi-infinite sequence of symbols which gets locally modified during execution. By default two symbols, 0 and 1, are used, but extended multi-symbol alphabets are also studied.
• The configuration of the machine at each step of the computation consists of the symbols on the tape, the tape head pointing at one of the tape positions, and a choice of one of the $n$ states, typically labeled with the first $n$ capital letters of the alphabet.
• The machine starts out in state A, with the tape consisting of a sequence of all zeros.
• At each step of the computation, the machine reads the symbol at the tape head, and based on its current state and the symbol it read, it chooses the parameters for the following actions:
  • Replace the symbol it has read with a possibly different one;
  • Move either left or right;
  • Change the state the machine is in.
• Each of the (current state, read symbol) pairs may also correspond to a halting transition, in which case the computation stops when the transition is reached. Most formally this is implemented by specifying an additional halt state, distinct from any of the $n$ states, which the machine can enter after performing a final write on the tape and moving the head one last time --- this matters when the exact score of the machine depends on the number of steps taken, or the number of non-zero symbols on tape. When machines of less than 26 states are being considered, the halt state is often denoted by Z.
  • It is common, however, to instead leave the the transition as undefined, with the understanding that it can either be interpreted as the guaranteed-optimal 1RZ halting transition, or otherwise extended during TNF enumeration.

Examples

The following machine is the longest-running 2-symbol 2-state Turing machine. It terminates after 6 steps.

BB(2) champion

	0	1
A	1RB	1LB
B	1LA	1RZ

The computation proceeds as follows:

0. 000 A[0] 000
1. 0001 B[0] 00
2. 000 A[1] 100
3. 00 B[0] 1100
4. 0 A[0] 11100
5. 01 B[1] 1100
6. 011 Z[1] 100

Standard text format

TODO

Directed-head formulation

TODO