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:
- The state qi is encoded by the letter 'D' followed by the letter 'A' repeated i times (a unary encoding)
- The tape symbol sj is encoded by the letter 'D' followed by the letter 'C' repeated j times
- 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:
- State: q1, input symbol: blank, action: print 1, move right, next state: q2
- 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:
DADDCCRDAA;DAADDCRDA;
But then, if we replaced each of the seven symbols 'A' by 1, 'C' by 2, 'D' by 3, 'L' by 4, 'R' by 5, 'N' by 6, and ';' by 7, we would have an encoding of the Turing machine as a natural number: this is the description number of that Turing machine under Turing's universal machine. The simple Turing machine described above would thus have the description number 313322531173113325317. There is an analogous process for every other type of universal Turing machine. It is usually not necessary to actually compute a description number in this way: the point is that every natural number may be interpreted as the code for at most one Turing machine, though many natural numbers may not be the code for any Turing machine (or to put it another way, they represent Turing machines that have no states). The fact that such a number always exists for any Turing machine is generally the important thing.
Read more about this topic: Description Number
Famous quotes containing the words description and/or number:
“The Sage of Toronto ... spent several decades marveling at the numerous freedoms created by a global village instantly and effortlessly accessible to all. Villages, unlike towns, have always been ruled by conformism, isolation, petty surveillance, boredom and repetitive malicious gossip about the same families. Which is a precise enough description of the global spectacles present vulgarity.”
—Guy Debord (b. 1931)
“In this world, which is so plainly the antechamber of another, there are no happy men. The true division of humanity is between those who live in light and those who live in darkness. Our aim must be to diminish the number of the latter and increase the number of the former. That is why we demand education and knowledge.”
—Victor Hugo (18021885)