display | more...

In Alan Turing's seminal 1936 paper, "On computable numbers, with an application to the Entscheidungsproblem", Turing gives the first descriptions of Turing machines and a universal Turing machine (UTM) in an attempt to resolve David Hilbert's Entscheidungsproblem. Description numbers, also sometimes called Godel numbers after their similarity to the numbers that appear in Godel's theorem, arise in encodings of Turing machines for a UTM, and play a key role in Turing's proof. As an example, say we have a Turing machine M with states q1, ..., qR, with initial state q1, tape alphabet consisting of the symbols S1, ..., Sm, with the blank denoted S0, and transitions giving current state, current symbol, operations performed (which involve overwriting the current symbol and moving the machine tape head left, right, or perhaps not moving it at all), and the next state. This Turing machine is encoded as input for the UTM as follows.

• The state qi is encoded by the letter 'D' followed by the letter 'A' repeated i times (a unary encoding).
• The tape symbol Sj encoded by the letter 'D' followed by 'C' repeated j times.
• Each of the transitions is encoded by giving the state, the input symbol, the symbol to write on the tape, the direction in which to move the tape head (expressed as the letters 'L', 'R', or 'N', meaning move left, right, or don't move respectively), and the next state to enter, all of them encoded as above.

The UTM's input consists of all the transitions for the input Turing machine separated by semicolons ';', thus giving our UTM the input alphabet {'A', 'C', 'D', 'L', 'R', 'N', ';'}, which consists of seven symbols. For example, if we have a simple Turing machine that alternates printing 0's and 1's forever on its initially blank tape, we would then have a two-state Turing machine with these transitions:

1. State: q1, Input Symbol: Blank, Action: Print 1 and move right, Next state: q2
2. State: q2, Input Symbol: Blank, Action: Print 0 and move right, Next state: q1

Using the above encoding, with Blank = S0, 0 = S1, and 1 = S2, we would have the encoding: