Search code examples
computer-scienceturing-machines

Turing's On Computable Numbers - I cannot understand how to reproduce examples

I just recently started reading some CS papers and one of the first ones was Turing's "On computable numbers" and in there he is providing an example of the machine configurations for printing the 010101 sequence. I understand how it should work, but I am struggling to understand why does it have two R moves in those operations:

m-config | symbol | operations | final m-config
         |  None  |     P0     |       b
    b    |   0    |   R, R, P1 |       b
         |   1    |   R, R, P0 |       b

If I start going through this then here are a couple of first steps:

Step 1: P0

Result:

0

Step 1: R, R, P1

0 1

Step 2: R, R, P0

0 1 0

Step 3: R, R, P1

0 1 0 1

So basically it works just fine, but the paper clearly states that this machine should print out 010101, without any blanks on tape. But because after printing we are always moving two times to the right then that means that we always leave one blank square on the tape. Can someone help me understand what am I doing wrong?

Solution

  • Turing defined the sequence computed by the machine this way:

    Computing machines.

    If an a-machine prints two kinds of symbols, of which the first kind (called figures) consists entirely of 0 and 1 (the others being called symbols of the second kind), then the machine will be called a computing machine. If the machine is supplied with a blank tape and set in motion, starting from the correct initial m-configuration, the subsequence of the symbols printed by it which are of the first kind will be called the sequence computed by the machine.

    The machine in the example is actually printing 0B1B0B1B0... on the tape but the sequence it computes is defined as the subsequence of 0B1B0B1B0... that consists of 0 and 1 only, thus 01010....
    In practice Turing is allowing for blanks in between the binary digits.

    I shamefully confess to have never read the original paper but I suppose this is possibly used to simplify the computation: allowing for blanks in between the digits spare the programmer/mathematicians from a recompacting (and boring) step.
    Basically this allow for a local scratchpad, you can use as many cells as you need near a digit as long as you erase them before moving to the next.