Example of Universal-machine Coding
- For those who would undertake the challenge of designing a UTM exactly as Turing specified see the article by Davies in Copeland (2004:103ff). Davies corrects the errors in the original and shows what a sample run would look like. He claims to have successfully run a (somewhat simplified) simulation.
The following example is taken from Turing (1936). For more about this example see the page Turing machine examples.
Turing used seven symbols { A, C, D, R, L, N, ; } to encode each 5-tuple; as described in the article Turing machine, his 5-tuples are only of types N1, N2, and N3. The number of each "m-configuration" (instruction, state) is represented by "D" followed by a unary string of A's, i.e. "q3" = DAAA. In a similar manner he encodes the symbols blank as "D", the symbol "0" is "DC", the symbol "1" as DCC, etc. The symbols "R", "L", and "N" remain as is.
After encoding each 5-tuple is then "assembled" into a string in order as shown in the following table:
| Current m-configuration | Tape symbol | Print-operation | Tape-motion | Final m-configuration | Current m-configuration code | Tape symbol code | Print-operation code | Tape-motion code | Final m-configuration code | 5-tuple assembled code | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| q1 | blank | P0 | R | q2 | DA | D | DC | R | DAA | DADDCRDAA | |
| q2 | blank | E | R | q3 | DAA | D | D | R | DAAA | DAADDRDAAA | |
| q3 | blank | P1 | R | q4 | DAAA | D | DCC | R | DAAAA | DAAADDCCRDAAAA | |
| q4 | blank | E | R | q1 | DAAAA | D | D | R | DA | DAAAADDRDA |
Finally, the codes for all four 5-tuples are strung together into a code started by ";" and separated by ";" i.e.:
- ;DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAAA;DAAAADDRDA
This code he placed on alternate squares—the "F-squares" -- leaving the "E-squares" (those liable to erasure) empty. The final assembly of the code on the tape for the U-machine consists of placing two special symbols ("e") one after the other, then the code separated out on alternate squares, and lastly the double-colon symbol "::" (blanks shown here with "." for clarity):
- ee.;.D.A.D.D.C.R.D.A.A.;.D.A.A.D.D.R.D.A.A.A.;.D.A.A.A.D.D.C.C.R.D.A.A.A.A.;.D.A.A.A.A.D.D.R.D.A.::......
The U-machine's action-table (state-transition table) is responsible for decoding the symbols. Turing's action table keeps track of its place with markers "u", "v", "x", "y", "z" by placing them in "E-squares" to the right of "the marked symbol" -- for example, to mark the current instruction z is placed to the right of ";" x is keeping the place with respect to the current "m-configuration" DAA. The U-machine's action table will shuttle these symbols around (erasing them and placing them in different locations) as the computation progresses:
- ee.; .D.A.D.D.C.R.D.A.A. ; zD.A.AxD.D.R.D.A.A.A.;.D.A.A.A.D.D.C.C.R.D.A.A.A.A.;.D.A.A.A.A.D.D.R.D.A.::......
Turing's action-table for his U-machine is very involved.
A number of other commentators (notably Penrose 1989) provide examples of ways to encode instructions for the Universal machine. As does Penrose, most commentators use only binary symbols i.e. only symbols { 0, 1 }, or { blank, mark | }. Penrose goes further and writes out his entire U-machine code (Penrose 1989:71–73). He asserts that it truly is a U-machine code, an enormous number that spans almost 2 full pages of 1's and 0's. For readers interested in simpler encodings for the Post-Turing machine the discussion of Davis in Steen (Steen 1980:251ff) may be useful.
Read more about this topic: Universal Turing Machine