A Programmable Prototype to Build Turing Machines

Home Alan TURING History Turing machine The actual experimental prototype Some diagrams of Turing machines for this prototype Presentations Presse Contact A new
machine
Machines Ideas Description How the machine operates Technologies First Turing machine Easy Calculations Sequences Interesting Colleges University Talks Videos



The first a-machines that Turing gives as examples : Enumerating whole numbers

As a slightly more difficult example we can construct a machine to compute the sequence 001011011101111011111...

The machine is to be capable of five m-configurations, viz. "o", "q", "p", "f", "b" and of printing "e", "x", "0", "1".

The first three symbols on the tape will be "ee0"; the others figures follow on alternate squares. On the intermediate squares, we never print anything but "x". These letters serve to "keep the place" for us and are erased when we have finished with them. We also arrange that in the sequence of figures on alternate squares there shall be no blanks..

Extract from "On computable numbers..." [Turing, 1936]
vol. 2:42, coll. " Proceedings of the London Mathematical Society ",1936 , p. 233

Publication d'Alan TURING 1936


 

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
    Return every 2 steps on the 'draft' spaces
    • 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.