Editing Universal Turing machine (section)

==Example of coding==
For those who would undertake the challenge of designing a UTM exactly as Turing specified see the article by Davies in {{harvp|Copeland|2004}}. Davies corrects the errors in the original and shows what a sample run would look like. He successfully ran a (somewhat simplified) simulation.

The following example is taken from {{harvp|Turing|1937}}. For more about this example, see [[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 "{{mvar|m}}{{nbh}}configuration" (instruction, state) is represented by "D" followed by a unary string of A's, e.g. "q3" = DAAA. In a similar manner, he encodes the symbols blank as "D", the symbol "0" as "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:

{|class="wikitable"
|-
! Current m{{nbh}}configuration
! Tape symbol
! Print-operation
! Tape-motion
! Final m{{nbh}}configuration
! Current m{{nbh}}configuration code
! Tape symbol code
! Print-operation code
! Tape-motion code
! Final m{{nbh}}configuration code
! 5-tuple assembled code
|-
| q1
 | {{CNone|blank}}
 | P0
 | R
 | q2
 | DA
 | D
 | DC
 | R
 | DAA
 | DADDCRDAA
|-
| q2
 | {{CNone|blank}}
 | E
 | R
 | q3
 | DAA
 | D
 | D
 | R
 | DAAA
 | DAADDRDAAA
|-
| q3
 | {{CNone|blank}}
 | P1
 | R
 | q4
 | DAAA
 | D
 | DCC
 | R
 | DAAAA
 | DAAADDCCRDAAAA
|-
| q4
 | {{CNone|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.:

{{block indent| ''';'''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):

{{block indent|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{{nbh}}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:

{{block indent|ee.''';''' .D.A.D.D.C.R.D.A.A. ''';''' '''z'''D.A.A'''x'''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.'''::'''......}}

Turing's action-table for his U-machine is very involved.

[[Roger Penrose]] provides examples of ways to encode instructions for the Universal machine using only binary symbols { 0, 1 }, or { blank, mark | }. Penrose goes further and writes out his entire U-machine code. 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.{{sfnp|Penrose|1989|pp=71–73}}

Asperti and Ricciotti described a multi-tape UTM defined by composing elementary machines with very simple semantics, rather than explicitly giving its full action table. This approach was sufficiently modular to allow them to formally prove the correctness of the machine in the [[Matita]] [[proof assistant]].{{sfnp|Asperti|Ricciotti|2015}}