A Multi-State Example 

The tape alphabet is {b, 0, 1}.

The set of states is {A, B, C}.

The instructions are:

       

(A, 0, B, b, R)
(A, 1, C, b, R)
(B, 0, B, 0, R)
(B, 1, C, 0, R)
(C, 0, B, 1, R)
(C, 1, C, 1, R)

 

Where b stands for the "blank" character.
The starting state is A and the tape is positioned so that the rightmost symbol is under the read/write head.



We try this on the input

10001

What does it do?

 

(A, 0, B, b, R)
(A, 1, C, b, R)
(B, 0, B, 0, R)
(B, 1, C, 0, R)
(C, 0, B, 1, R)
(C, 1, C, 1, R)
Start
 
1
0
0
0
1
       
A
       
 
1
0
0
0
       
 
C
       
   
1
0
0
1
       
   
B
       
     
1
0
0
1
     
     
B
     
       
1
0
0
1
   
       
B
   
         
 
0
0
0
1
 
HALT
         
C
 

How about:

10000?

 

(A, 0, B, b, R)
(A, 1, C, b, R)
(B, 0, B, 0, R)
(B, 1, C, 0, R)
(C, 0, B, 1, R)
(C, 1, C, 1, R)
Start
 
1
0
0
0
0
       
A
       
 
1
0
0
0
       
 
B
       
   
1
0
0
0
       
   
B
       
     
1
0
0
0
     
     
B
     
       
1
0
0
0
   
       
B
   
         
 
0
0
0
0
 
HALT
         
C
 

Try 10101


Last Updated 01/05/2004
L.Heath, 2000
Modified by J.A.N. Lee, 2004