Constructing this machine with the prototype
Adaptation to the prototype :
-
The rough work
The Turing machine systematically leaves one space between all the figures that constitute the expected result. Turing uses this space as "rough work" and writes
in it the letter x, as needed. Since these spaces are always located on alternate squares, the letter x is not necessary and to use the prototype,
we will use the figure 1 instead of that letter x. The two letters ee included in the first 2 squares will simply be replaced by 0.
-
Compact writing of the table of transitions
Turing indicates that the moves can be grouped together in the form of R, Px, L, L, L for example.
For the prototype, this transition will be written in the form of 3 transitions including only one move L each.
Comments on the table of transitions -->
-
Configuration b :
The letters that correspond to the configuration, i.e. 00_0, were placed manually on the tape.
-
Configuration o :
Originally, it included 4 moves. It will be translated into 4 states (here from 1 to 4).
Writing the 1's of the "rough work" to the right of each 1 in a sequence.
Positioning on the 0 at the beginning of this sequence.
Moving to configuration q
-
Configuration q :
Here, it is translated by states 5 and 6
Moving the head to the right two by two and writing a new 1.
Moving one square to the left and moving to configuration p.
-
Configuration p :
Here it is translated by states 7 and 8
Moving back two by two on the �rough work� squares
- This move ends on a 1 : Erasing this 1 and moving to configuration q
- This move ends on a 0 : It is the 0 to the left of the initial 0. Moving to configuration f
-
Configuration f :
Here it is translated by states 9, 10 and 11
Moving the head to the right two by two and writing a new 0.
Moving one square to the left and moving to configuration o.
|
