Turing Computation of the Natural Numbers

by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]

[Central Entry Directory]
[Computation Entry Directory]

Turing Computation

of the Natural Numbers

We will now build from our previous post on Turing machines. What we want is a mechanical computation of the natural numbers.

[I obtain the following program from Peter Bradley's wonderful animated site on Turing Machines.]

Our abstract machine will compute the natural numbers and display them in binary. So it is a "binary counter" machine.

This is its program, displayed as a "machine table." The S represents the number that the machine is reading. The subscript '0' means it would be a zero, and the subscript '1' means it is a one.

The q's stand for the two different instructions. L means to move left. R means to move right. There are two boxes for each q instruction, because the machine will see either of two symbols (1 or 0), and according to which one, it will perform some distinct task. We could articulate the instructions this way.

q1) If the scanned symbol is zero, write a zero overtop of it, move to the left, and begin instruction q1. If the scanned symbol is one, write a one overtop of it, move to the right, and begin instruction q2.

q2) If the scanned symbol is zero, write a one instead, move to the left, and begin instruction q1. If the scanned symbol is one, write a zero instead, move to the right, and begin instruction q2.

We will follow it through all the steps leading to its count of four.

It begins on a zero.

All the other boxes are zero except for one. At two spaces to the left of the starting point, there is a '1'. We do not read this with the number. Its function is to 'bump' the machine back to the right so it may continue its adding. All the boxes to the right of the bumper are the binary digit places that display each new counted number as it is added. However, this display shows them inversely. Hence we need to think of the ascending digit places moving to the right. So normally 100 equals four in binary. But here it would be displayed as 001.

So the machine finds itself at the second zero. We place a yellow arrow wherever the machine is found at the start of the given instruction. It always moves at the end of the instruction. We display its direction with black arrows.

We begin at the first instruction q1. Because the machine starts at a zero, we look to S0. It tells the machine to write a zero, and to move to the left. There is already a zero there, so nothing changes.

Likewise for the next step. Instruction q1 repeats.

But now the machine stands above a '1'.

It writes a '1' again, then it moves to right and begins instruction q2.

At this box there is a zero. So the machine replaces it with a '1', moves the left, and begins instruction q2. At this point, we have our first counted value: 1

The number it scans next is a '1', so it writes a '1' over it, moves to the right, and begins instruction q2.

Here the machine finds a '1'. So it replaces it with a zero, moves to the right to begin q2. But notice the similarity to when we clear the binary abacus.

At the next place it finds a zero. Instruction q2 tells it then to write a '1' instead and move to the left. This is equivalent to the carry procedure on the binary abacus.

So we see our first instance of clear and carry performed by the Turing Computer.

It now sees a zero. Instruction q1 tells it to write another zero, move to the left, and begin instruction q1.

It arrives upon the bumper. Instruction q1 tells it to write another '1' over it, move to the right, and begin instruction q2.

Now it sees a zero in the units place of our number display. Instruction q2 tells it to write a '1', move to the left, then begin instruction q1. In this way, we have added another number to get three.

It hits the bumper again, so it goes to the right and begins instruction q2.

Now it sees a '1' in the units place. Instruction q2 tells it to write a '0' instead, move to the right, and begin instruction q2. Here again is a clear procedure.

It sees another '1' in the next digit place. Instruction q2 tells it to write a zero, move to the right, and begin instruction q2. This is the second part of the clear/carry procedure.

Now it sees a '0'. Instruction q2 tells it to replace the '0' with a one, move the left, and begin instruction q1. This is the carry procedure that gets us to four. Now, the machine repeats the same clear/carry process as it had before.

Given an infinite amount of time, it will display the infinity of natural numbers.

See Peter Bradley's site on Turing Machines