Small two-state

From 2009.igem.org

Turing Machine

Look at the following set of instructions.

The leftmost column of the table shows us that this particular Turing machine has two internal states of the box which we have labeled as A and B to distinguish them. Now consider the third row of the set of instructions. This set of instructions is interpreted as follows--“If the machine is in state B and the machine reads the mark 0 on the tape, then the internal state changes to A, the mark on the tape is changed from 0 to 1 and the machine stops.” Similarly, the first row tells the machine-“If you are in state A and you read the mark 0 on the tape, you change your internal state to A, change the mark on the tape from 0 to 0 and move one step towards the right so as to read the next mark on the tape.”

Now consider the following tape:

Here we assume, that because the tape is infinite, there are infinitely many zeros to the right of this tape and an infinitely many zeros to the left of this tape. That is to say we have considered only a segment of the potentially infinite tape. The infinite tape would look something like this.

If this tape is fed to the Turing machine let us see what happens.

The Turing machine reads a zero on the tape [Note- initially the machine is in state A] which is somewhere to the left of our given sequence. According to the first instruction, it changes its internal state to A, changes the tape mark to 0, and moves one step towards the right. In essence there is no change in the tape but that the machine has moved forward one step along the tape. The machine will go on repeating this until it reads the first 1 on the tape. When this occurs, the machine will carry out the second set of instructions because the machine is in internal state A and it reads a 1 on the tape. It will subsequently change the 1 to 1 and change its internal state to B moving one step to the right. Then it encounters the second 1 on the tape which it changes to 1, changes its internal state to B and moves one step towards the right [in accordance with the fourth instruction] This will continue until the machine encounters the 0 which proceeds the sequence of six 1’s. This zero will be changed to 1 and the internal change will be changed to A and the machine will stop. After the action of this entire process the new tape will look like this:

Note that there is a sequence of seven 1’s as compared to the original six present initially on the earlier tape. So this Turing machine which we shall call UN+1 increases the sequence of 1’s by one unit, i.e. the new sequence consists of another consecutive 1 on the tape. The name UN+1 been given because if we consider the sequence of 1’s as the unary representation of any natural number, then UN+1 adds 1 to that number. {In the unary system 2 is represented as 11 while 4 is represented as 1111.}

Thus we have seen how the Turing machine performs a calculational procedure mechanically and deterministically.

Further Details

Go Back