Turing machine

From BusyBeaverWiki
Jump to navigation Jump to search

Turing machines are a model of computation first introduced by Alan Turing in 1936.[1] 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 states, typically labeled with the first 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 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

To facilitate communication, a standard succinct textual format for the transition tables of Turing machines has been agreed upon.[2] The format supports Turing machines with up to 25 states and up to 10 symbols. As an example, the BB(2) champion listed above would be specified as 1RB1LB_1LA1RZ (bbch). A full specification of the format follows.

  • Symbols are represented by digits, starting from 0
  • States are represented by letters, starting from A
  • Directions are specified as either L (left) or R (right)
  • Each transition is encoded by listing the written symbol, direction, and next state, in that order. For example: 1RB
  • The transitions for a particular state are listed one after another. For example: 1RB1LB
  • The descriptions for each state of the machine are listed by joining them with underscores, forming the full description of the machine.
  • No unused symbols or states may be present — if state D is in use, states A through C must also be.
  • Halting transitions can be represented by any listing as the next state any capital letter larger than the number of states, but use of H or Z is encouraged for readability.
  • Undefined transitions are represented as ---

See also

References

  1. Turing, A.M. (1937). "On computable numbers, with an application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. 58: 230–265 https://doi.org/10.1112/plms/s2-42.1.230
  2. Ligocki, S. (2022) "Standard TM Text Format". https://www.sligocki.com/2022/10/09/standard-tm-format.html