In case you forgot: how to evaluate a Turing Machine
7Simple video on how to evaluate a Turing Machine.
Take note of the arrows, they show which state to move to after performing an operation on the tape.
The tape is initialized with the value 101 (5) in binary.
A rule looks like this 1/0,R
The rules are simple. 0/1,R means read a zero, replace it with 1, move right on the tape.
1/0,L means read a 1, replace it with a zero and move left on the tape.
0/0,N would mean read a zero, replace a zero and don't move.
Special cases:
Ɛ = _ _ _ ... = ... _ _ _
meaning the empty string Ɛ (epsilon) is composed of an arbitrary number of blanks.
For example, if we had a tape: _ 101 _
|
and were in state q0 this would give us the configuration: (Ɛ, q0, 101)
because it is implied that ... _ _ _ 101 _ _ _ ... infinitely.
Whereas the case when any number larger or equal 1 of blanks is sandwiched between non blanks:
_ _ 1_ 101_
|
for example would be (Ɛ, q0, 1_101)
and for example:
_ _ 1_ 101_
|
would be (1_, q0, 101)