Description number

Description numbers are numbers that arise in the theory of Turing machines. They are very similar to Gödel numbers, and are also occasionally called "Gödel numbers" in the literature. Given some universal Turing machine, every Turing machine can, given its encoding on that machine, be assigned a number. This is the machine's description number. These numbers play a key role in Alan Turing's proof of the undecidability of the halting problem, and are very useful in reasoning about Turing machines as well.

An example of a description number

Say we had a Turing machine M with states q1, ... qR, with a tape alphabet with symbols s1, ... sm, with the blank denoted by s0, and transitions giving the current state, current symbol, and actions performed (which might be to overwrite the current tape symbol and move the tape head left or right, or maybe not move it at all), and the next state. Under the original universal machine described by Alan Turing, this machine would be encoded as input to it as follows:

1. The state qi is encoded by the letter 'D' followed by the letter 'A' repeated i times (a unary encoding)
2. The tape symbol sj is encoded by the letter 'D' followed by the letter 'C' repeated j times
3. The transitions are encoded by giving the state, input symbol, symbol to write on the tape, direction to move (expressed by the letters 'L', 'R', or 'N', for left, right, or no movement), and the next state to enter, with states and symbols encoded as above.

The UTM's input thus consists of the transitions separated by semicolons, so its input alphabet consists of the seven symbols, 'D', 'A', 'C', 'L', 'R', 'N', and ';'. For example, for a very simple Turing machine that alternates printing 0 and 1 on its tape forever:

1. State: q1, input symbol: blank, action: print 1, move right, next state: q2
2. State: q2, input symbol: blank, action: print 0, move right, next state: q1

Letting the blank be s0, '0' be s1 and '1' be s2, the machine would be encoded by the UTM as: