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.
*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.
Last
Updated 01/05/2004
© L.Heath,
2000
Modified by J.A.N. Lee, 2004