(idea) by dido Sun Sep 28 2003 at 6:29:41

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:

DADDCCRDAA;DAADDCRDA;

Now, note that each of the seven symbols in the UTM input alphabet may be replaced by numbers, with 'A' with '1', 'C' with '2', 'D' with '3', 'L' with '4', 'R' with '5', 'N' with '6', and ';' with '7', so a Turing machine encoding may also be represented as a number. This is its description number. The above Turing machine has description number 313322531173113325317. There is an analogous process for any other universal Turing machine and how it would encode other Turing machines (this particular code is that used by Turing's own universal machine). The point is that any natural number may be interpreted as the code for at most one Turing machine, though many natural numbers may not be the code of any Turing machine. Determining whether or not an arbitrary natural number is a valid description number should also be decidable, e.g. a function d(e) which is 1 if e represents a valid Turing machine and 0 if it doesn't must be a total recursive function, otherwise none of the other subsequent machinery for use with description numbers will work correctly. (Thanks to ariels for pointing this bit out.) Just as with Godel numbers, it is usually not necessary to actually calculate such a desription number in this way; merely knowing that such a description number always exists for any possible Turing machine is usually sufficient.

The fact that we can actually encode Turing machines as numbers gets us into real trouble. From here, we can very easily prove that the halting problem is undecidable by a technique similar to Cantor diagonalization. First, let us denote U(e, x) as the action of the UTM given the description number e and input x, giving 0 if e is not the description number of any Turing machine. Now, let us suppose that there were an algorithm capable of deciding whether a particular Turing machine will halt on all inputs or not, given its description number, call it TEST(e), which returns 1 if the Turing machine corresponding to the description number e will halt on every input, and 0 if it won't. We should then be able to construct a function δ(k), that is defined as U(k, k) + 1 if TEST(k) == 1 and 0 if TEST(k) == 0. By definition δ is defined for every input and is thus total recursive. Let e be the description number for the Turing machine computing δ. Thus δ(x) = U(e, x) and TEST(e) == 1. But by definition δ(e) = U(e, e) + 1, which leads to a contradition, thus our initial supposition is false, and thus determining whether arbitrary Turing machines halt on all inputs or not is undecidable. (Gee, have I just settled Entscheidungsproblem?)

I like it! 1 C!