A Turing Machine (TM) For The Universal Turing Machine (UTM)
This machine duplicates a string of "10" symbols. It is a two symbol version of the program in the Finite State Machine of the Turing Machine in Conway's Game of Life which doubled string of symbol "1". The following state transition diagram describes the machine. The symbol at the foot of the arrow is that under the read/write head and the symbols part way along are; the one to write (if different) and the direction of movement of the head.
This machine is preprogrammed into the Java TM simulator. It is coded into transitions for the Universal Turing Machine as shown in the following list in the order they appear on the tape.
The UTM starts the TM in state S1 with a 1 under the read/write head (transition T2).
The order in which the transitions are coded makes a big difference to the length of tape required and the time to perform an average cycle of machine T. I think the above order is quite close to the optimum but I would not be surprised is a slightly better order existed.
Transition
Number State Value Write Move Next
for 0 Next
for 1 Coding
T1 S2
S4 0
0/1 1 L T2 T3 101C11
T2 S1
S3 1
0 1 R T1 T3 110C11
T3 S3 1 1 L T1 T1 1000C00
T4 S2 1 1 R T6 T2 1111C00
T5 S6 1 1 L Halt T7 1010C11
T6 S1 0 0 L Halt T7 0010C1
T7 S5 1 0 L - T5 0010C00
|
Site by Paul Rendell. |
Last Update 13 February 2010 |
Comments to Paul Rendell |