In 1936, Alan Turing thought up what he called the amachine (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
 change the character on that segment (say for example if it sees a 0 it could erase the 0 or write a 1 instead)
 leave it alone
 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.
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.
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
<1^{st} number>, blank space, <2^{nd} 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 
Move Right 
State 1  Move Right Remain in state 1 
Move Left 
State 2 
Erase symbol 

State 3  Move Left 
Write * 
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 1^{st} 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 2^{nd} instance, it is in state 0 and sees * => It will move right and remain in state 0.
*,*,*,*,*,_,*,*,_,_,_,_ …
At the 3^{rd} instance, it is in state 0 and sees * => It will move right and remain in state 0.
*,*,*,*,*,_,*,*,_,_,_,_ …
At the 4^{th} instance, it is in state 0 and sees * => It will move right and remain in state 0.
*,*,*,*,*,_,*,*,_,_,_,_ …
At the 5^{th} instance, it is in state 0 and sees * => It will move right and remain in state 0.
*,*,*,*,*,_,*,*,_,_,_,_ …
At the 6^{th} 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 7^{th} instance, it is in state 1 and sees * => It will move right and remain in state 1
*,*,*,*,*,_,*,*,_,_,_,_ …
At the 8^{th} instance, it is in state 1 and sees * => It will move right and remain in state 1
*,*,*,*,*,_,*,*,_,_,_,_ …
At the 9^{th} 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 9^{th} 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 10^{th} 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 11^{th} 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 1^{st} 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!
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.
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
Pingback: Four views on Artificial Consciousness  klal1984·