CIT 594 Simulating a TM with a Modified Post Correspondence Problem
Spring 2012, David Matuszek

Turing Machine Evaluation of 100
q0 1 1 q0 R
q0 0 0 q0 R
q0 # # q1 L
q1 1 1 qA R
q1 0 1 qA R
Conventional (1-line) evaluation:
q0100 ⇒ 1q000 ⇒ 10q00 ⇒ 100q0 ⇒ 10q10 ⇒ 101qA

R/W head shown just before tape symbol it is on.
# represents a space (not used above).

start  
#
#q0100#
                   
move right  
q00
0q0
 
q01
1q0
 
q10
1qA
 
q11
1qA
       
move left  
#q0#
q1##
 
0q0#
q10#
 
1q0#
q11#
           
copy  
0
0
 
1
1
 
#
#
           
clean up  
0qA
qA
 
1qA
qA
 
#qA
qA
 
qA0
qA
 
qA1
qA
 
qA#
qA

terminate

 
qA##
#
                   

#
#q0100#
q01
1q0
0
0
0
0
#
#
1
1
q00
0q0
0
0
#
#
1
1
0
0
q00
0q0
#
#
1
1
0
0
0
0
0q0#
q10#
1
1
0
0
q10
1qA
#
#
1
1
0
0
1qA
qA
#
#
1
1
0qA
qA
#
#
1qA
qA
#
#
qA##
#
                              bad