The Turing Machine

In 1936, Alan Turing thought up what he called the a-machine (automatic machine). To understand what this machine did, consider a very long strip of paper divided into segments (like a toilet roll). On each segment is written a character from a finite set of characters or is left blank. So for example, we may have 3 characters A, B and C so every segment would have an A or a B or a C or a blank space (_). Another example would be binary where every segment would have a 0 or a 1 or a blank space. You may have:

0, 0, 0, _, 1, 0, 1, _, 0 …

This paper tape would be fed into the machine. The machine would read the characters one at a time. After reading a character, it could decide to either

  1. change the character on that segment (say for example if it sees a 0 it could erase the 0 or write a 1 instead)
  2. leave it alone
  3. erase the character and leave the segment blank

At any given time, which one of these 3 options it takes depends on the internal state of the machine. It would then move to the next segment either to the right or left of the segment it has just read. Whether it moved right or left again depended on its state.

turingmachine2

If you are not comfortable with programming or mathematics or simply don’t understand what I mean by ‘state’, please bear with me, it is actually simpler than I am making it sound and the results this leads to are very profound indeed to merit your patience.

turingmachine

Lets clarify the meaning of the term state with an example. Say we want a Turing Machine to add 2 numbers. We can choose to write the numbers in unary, that is to say we have only 1 symbol, *. So we can write

1 = *

2 = **

5 = *****

10 = **********

Now if we want to add 2 numbers, we can put them on the tape like this

<1st number>, blank space, <2nd number>

So of we want to do 5+2, we can write on the paper strip,

*,*,*,*,*,_,*,*,_,_,_,_ …

This paper strip would then be fed into the Turing Machine. Also fed into the Turing Machine will be a table of states like the one below. Each row represents a different state and each column represents a symbol it can see.

Symbol A Symbol B Symbol C Symbol _
State 0 Cell 0A Cell 0B Cell 0C Cell 0_
State 1 Cell 1A Cell 1B Cell 1C Cell 1_
State 2 Cell 2A Cell 2B Cell 2C Cell 2_
State 3 Cell 3A Cell 3B Cell 3C Cell 3_
State 4 Cell 4A Cell 4B Cell 4C Cell 4_
State 5 Cell 5A Cell 5B Cell 5C Cell 5_

Table 1: A general state for a Turing Machine

So if the Turing Machine is in state 3 and we see symbol B, then it should do whatever is written in cell 3B. In our example, we would have 2 columns for the 2 possible symbols * and _.

* _

State 0

Move right
Remain in state 0

Move Right
Go to State 1

State 1 Move Right
Remain in state 1

Move Left
Go to State 2

State 2

Erase symbol
Move Left
Go to state 3

State 3 Move Left

Write *
STOP

Table 2: State table for Addition in a Turing Machine

At the start the Turing Machine is always in state 0. Now, lets say it starts reading the paper strip containing our example for 5+2 *,*,*,*,*,_,*,*,_,_,_,_ … from left to right. The highlight indicates the segment being read at a given time instance by the Turing Machine.

*,*,*,*,*,_,*,*,_,_,_,_ …

At the 1st instance, it is in state 0 and sees * => It will move right and remain in state 0 (see cell 0* in table 2).

*,*,*,*,*,_,*,*,_,_,_,_ …

At the 2nd instance, it is in state 0 and sees * => It will move right and remain in state 0.

*,*,*,*,*,_,*,*,_,_,_,_ …

At the 3rd instance, it is in state 0 and sees * => It will move right and remain in state 0.

*,*,*,*,*,_,*,*,_,_,_,_ …

At the 4th instance, it is in state 0 and sees * => It will move right and remain in state 0.

*,*,*,*,*,_,*,*,_,_,_,_ …

At the 5th instance, it is in state 0 and sees * => It will move right and remain in state 0.

*,*,*,*,*,_,*,*,_,_,_,_ …

At the 6th instance, it is in state 0 but sees _ => It will move right and go to state 1 (see cell 0_ in table 2)

*,*,*,*,*,_,*,*,_,_,_,_ …

At the 7th instance, it is in state 1 and sees * => It will move right and remain in state 1

*,*,*,*,*,_,*,*,_,_,_,_ …

At the 8th instance, it is in state 1 and sees * => It will move right and remain in state 1

*,*,*,*,*,_,*,*,_,_,_,_ …

At the 9th instance, it is in state 1 and sees _ => It will move left and go to state 2 (see cell 1_ in table 2)

*,*,*,*,*,_,*,*,_,_,_,_ …

At the 9th instance, it is in state 2 and sees * => It erases the * symbol and leaving the segment blank. It also moves left and goes to state 3 (see cell 2* in table 2). The changed strip now looks like this:

*,*,*,*,*,_,*,_,_,_,_,_ …

We proceed further,

*,*,*,*,*,_,*,_,_,_,_,_ …

At the 10th instance, it is in state 3 and sees a * => It moves left and remains in state 3 (see cell 3* in table 2)

*,*,*,*,*,_,*,_,_,_,_,_ …

At the 11th instance, it is in state 3 and sees a _ => It writes a * in the segment and stops (see cell 3_ in table 2)

*, *, *, *, *, *, *, _, _, _, _, _, …

The program has stopped and we have our answer, 7 *s indicating that 5+2 = 7. Note that the state table I have given above will work for any 2 natural numbers no matter how big. So the same program could make the machine add 342352 + 1257457 and give, we whatever that is.

For more examples of such state tables for subtraction, string matching, anagram checking etc. look in the 1st reference below.

This is cumbersome, but relatively straightforward. Now for the good bit, the part I promised you. Alan Turing proved that given enough time, paper and the right set of (finite) symbols and state table this dumb Turing Machine could do anything that any computer could ever do!

intel

Think about it, an Intel Xeon processor may have gigahertz of clock speed and dozens of cores, but there is nothing that it can do that cannot be done by a slow poke Turing Machine. All of computer design is simply building faster machines all of which can do no more than what a Turing Machine does. Even a 100 years later, no computer built on principles we understand (yes, Quantum computers too) could ever do anything that a Turing Machine could not.

supercomputer

But that’s not the end of the story, is there anything that a Turing Machine cannot do, even with the longest paper strip and the most complicated state table? This would then be something no computer could ever do.

Well that I hope will be the subject of another post.

 

References

[1] Paul Hoffman, Archimedes’ Revenge: The Joys and Perils of Mathematics

[2] Roger Penrose, Shadows of the Mind: A Search for the Missing Science of Consciousness

Advertisements

One response to “The Turing Machine

  1. Pingback: Four views on Artificial Consciousness | klal1984·

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s