Turing Machine Example

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

The set of states is {A}.

The instructions are:

(A, 0, A, 1, L)

(A, 1, A, 0, L)

 

The starting state is A and the tape is positioned so that its leftmost 0 or 1 is under the read/write head.



We can run through the configurations of the Turing machine on a sample input, say:

*10001*

When does it halt?

 

(A, 0, A, 1, L)

(A, 1, A, 0, L)

 

Start
*
1
0
0
0
1
*
State and position =>
A
New Tape
*
0
0
0
0
1
*
State and position =>
A
New Tape
*
0
1
0
0
1
*
State and position =>
A
New Tape
*
0
1
1
0
1
*
State and position =>
A
New Tape
*
0
1
1
1
1
*
State and position =>
A
New Tape
*
0
1
1
1
0
*
HALT!
A



  It would appear that this machine changes 1's to 0s and 0s to 1s everywhere. Check this out with other examples.


CS1104 Main Page
Last Updated 01/05/2000
© L.Heath, 2000