The Turing Machine: A blueprint for the computer
Subha Das Mollick
A computer would deserve to be called intelligent if it could deceive a human into believing that it was human. – Alan Turing
“Without Alan Turing, Stanford University, Silicon Valley and the world would be a very different place. The advancement of our species in the past 200 years after the industrial revolution has been marked by increasing mastery of machines and enslavement of the population to its cause. Inspired by the use of perforated cards and the analytical engine of Charles Babbage and Ada Lovelace, Alan Turing conceived the Universal Machine and enabled to develop the modern computing machinery,” said a Stanford University Professor, in his introductory note to a talk by Prof. Jack Kaplan, a Turing scholar from Cambridge University, New Zealand. The year was 2012, the year of the centenary celebration of Alan Turing.
Alan Turing was an English mathematician, logician, computer scientist, the first computational biologist, the father of what would later become artificial intelligence, and he was a modern philosopher of the mind. His contribution in cutting short the WW II by two years and saving millions of lives in the process has been celebrated in two films – Imitation Game (2014) and Enigma (2001). What the Stanford Professor or the films did not mention was Turing’s connection to India. Turing’s father was an officer in the Indian Civil Service, posted in Chhatrapur, in the Bihar province of British India. His grandfather had been a General in the Bengal Army. Turing’s maternal grandfather was the Chief Engineer with the Madras Railways. However, Turing himself had never travelled east of England.
From an early age Alan Turing had displayed extraordinary merit in mathematics and logical thinking. Not all his teachers appreciated his unique gift. Alan Turing’s headmaster at Sherborne Public School wrote to his parents, “I hope he will not fall between two stools. If he is to stay at public school, he must aim at becoming educated. If he is to be solely a Scientific Specialist, he is wasting his time at a public school.”
In 1936, in his very early 20s, he completely unexpectedly invented the fundamental principles of the modern computer. Turing was working on an abstract problem of mathematics, “On Computable Numbers, with an Application to the Entscheidungs problem“. Turing proved that a “universal computing machine” would be capable of performing any conceivable mathematical computation if it were representable as an algorithm.
No one would have thought that such abstruse, arcane work could have led to any practical value whatsoever – let alone a machine that would change all our lives. But it did. The Turing machine is a theoretical concept of an all purpose machine. The concept central to this machine is the idea of stored programmes. Turing’s machine was a blueprint on paper. The actual engineering came much later. Turing showed that by inserting different programmes in the memory of what he called the Universal Turing Machine, a computer could be made to carry out any task for which a programme could be written. The beauty of his idea was that a single machine could change itself chameleon – like from a machine dedicated to a particular task, into a machine dedicated to a completely different task – from word processor to calculator to chess opponent. Today we all own a physical realization of the universal Turing machine. We switch on our PCs and choose the application for the task we want the machine to perform. For us, Turing’s idea of a one stop shop computing machine seems as obvious as the wheel or the arch. But in 1936, when engineers thought in terms of building different machines for different tasks, Turing’s idea of a single machine carrying out multiple tasks was revolutionary.
When Alan Turing came up with the idea of a universal machine, he had in mind the simplest computing model powerful enough to calculate all possible functions that can be calculated. The blueprint of the simplest Turing machine is as follows:
It consists of an infinitely-long tape which acts like the memory in a typical computer, or any other form of data storage. The squares on the tape are usually blank at the start and can be written with symbols. In this case, the machine can only process the symbols 0 and 1 and ” ” (blank), and is thus said to be a 3-symbol Turing machine.
At any one time, the machine has a head which is positioned over one of the squares on the tape. With this head, the machine can perform three very basic operations:
- Read the symbol on the square under the head.
- Edit the symbol by writing a new symbol or erasing it.
- Move the tape left of right by one square so that the machine can read and edit the symbol on a neighbouring square.
A Turing machine is at a ‘start state’ when it begins to run a programme. It is at ‘current state’ while the programme runs. When the task is completed, it is at a ‘halt state’. If the ‘halt’ command is not incorporated into the programme, it will continue running indefinitely. If a Turing machine is used for the computation of functions it only has one end state. When the machine comes to that state it is halted and the result of the function (depending on the input) can be found on the tape. Here is a trivial example:
Let us try printing the symbols “1 1 0” on an initially blank tape:
First, we write a 1 on the square under the head:
Next, we move the tape left by one square:
Now, write a 1 on the new square under the head:
We then move the tape left by one square again:
Finally, write a 0 and that’s it!
Here is the list of commands in a nutshell:
Symbol read | Write instruction | Move instruction |
---|---|---|
Blank | Write 1 | Move tape to the left |
Blank | Write 1 | Move tape to the left |
Blank | Write 0 | Move tape to the left |
But this is incomplete because the machine has not been asked to stop. It will endlessly go on reading the blank square and the tape will go on ticking. To stop the machine after the task is completed, we have to add one more set of instructions. The table below is called a state table. If the machine comes to a ‘stop state’, it means end of task. ‘State10’ means, it has to continue. State 0, on the other hand, means that the machine has to get into action once again. If in the last row in the table below, instead of ‘Stop state’, ‘State 0’ is written, the machine will repeat the read-write-move sequence.
State | Symbol read | Write instruction | Move instruction | Next state |
---|---|---|---|---|
State 0 | Blank | Write 1 | Move tape to the left | State 1 |
Blank | Write 1 | Move the tape to the left | State 1 | |
Blank | Write 0 | Move the tape to the left | Stop state |
The machine can also be programmed to erase what it has written and write 001 instead. The algorithm will be as follows:
State | Symbol read | Write instruction | Move instruction | Next state |
---|---|---|---|---|
State 0 | 0 | Write 1 | Move the tape to the right | State 1 |
1 | Write 0 | Move the tape to the right | State 1 | |
1 | Write 0 | Move the tape to the right | Stop state |
When the machine reads a blank symbol, the machine is directed to a stop state and the program terminates.
The Turing thesis states that all computers are only as powerful as a Turing machine. This statement can be used to argue whether a problem is solvable by computers or not. A universal Turing machine serves as a standard for evaluating all computational systems. A system that can complete a universal Turing machine is called ‘Turing complete’.
Turing’s development of the concept of the Turing machine came to a halt when he was summoned to break the Enigma Code.
In 1939, Alan Turing was summoned to the war time cryptoanalytic headquarters Bletchley Park, where he was asked to join the team engaged in decrypting the German Enigma Code. He had been working on the Enigma Code for several months before the war broke out. Happy to work alone on a problem that defeated others, Turing cracked the system at the end of 1939, but it required the capture of further material by the Navy, and the development of sophisticated statistical processes, before regular decryption could begin in mid-1941.
Turing always believed that “Intellectual activity consists mainly of various kinds of search.” He told his bosses at Bletchley Park that to decode a machine that has 159 X 1018 possibilities and changes its setting every 24 hours, it is not possible for the human intellect to carry out the search. A machine is required.
The Polish cryptographers had developed a machine called Bomba. Turing improved upon this machine and developed the Bombe, a far more powerful device, capable of breaking the Enigma code if a small portion of the plain text could be guessed correctly.
The electromechanical engine Bombe searched for the crucial settings of the German Enigma machine. Each of the cylinders mimicked one of the three wheels of the Enigma machine. The Bombe speeded things up by using heuristic search. A heuristic cuts down on the amount of searching required. It is a faster process than a systematic thorough search, but does not always guarantee a correct answer. It is like looking for the keys where you are most likely to have dropped them last night. You are very likely to get the keys, but there is no 100 percent guarantee. Computerized chess programmes are based on heuristic search. Turing applied the same logic to the Bombe machine, although the term ‘heuristic’ was coined much later. The Bombe was the first milestone on the road to modern Artificial Intelligence.
By the end of 1946, Bletchley Park was breaking two enigma messages every minute. There were about 200 Bombes in and around Bletchley Park. At Bletchley Park, Turing was acquainted with telecommunication engineers who acquainted him with electronics. Turing realized that machines built with electronic circuitry would work much faster and more efficiently than electromechanical machines.
After the War, Turing joined the National Physical Laboratory in London and turned his creative energy to build the physical version of the Turing machine – the stored programme computer. He borrowed the ideas of electronic circuitry using valves.
But Neumann had won the race in Manchester. Neumann had been his professor at Princeton and his colleague at Bletchley Park. After the War, Neumann had joined the University of Manchester. There, in his team, he had hired two extraordinary engineers who got the first stored programme computer run in June 1948. The two engineers had learnt the basics of computers by attending a series of lectures that Turing gave in 1946 and 1947. The machine was called Manchester Mark 1.
ENIAC, the world’s first electronic computer was developed by the University of Pennsylvania in 1946. It was Turing-complete, digital, and could solve “a large class of numerical problems” through reprogramming. But the ENIAC did not use the concept of stored programmes of the Universal Turing Machine. To re-programme the ENIAC, one had to change the hardware – alter the wiring, change the valves and so on. It could take anything from a day to a week.
A pilot model of the automatic computing engine ACE was demonstrated to the press in December 1950 at Bushy House, the headquarters of National Physical Laboratory in London. ACE had a speed of 1 Mega Hertz. Even though it was physically smaller, with less memory, it was faster than all the other computers. Keeping the hardware to a minimum and putting the burden on the software was what Turing believed in.
In 1948 Turing wrote the first manifesto of Artificial Intelligence. He called it “Intelligent machinery”. In this manifesto he mooted the ideas of logical search, generic algorithm and connectionist learning.
Alan Turing will be remembered for three key ideas:
• his own 1936 concept of the universal machine
• the potential speed and reliability of electronic technology
• the inefficiency in designing different machines for different logical processes.
References
- https://www.youtube.com/watch?v=AgW6HplOZV0
- http://www.turing.org.uk/publications/dnb.html
- Stanford University video: Turing: Pioneer of the Information Age.
The author is a media teacher and documentary filmmaker. She is also the secretary of Bichitra Pathshala. She may be reached at subha.dasmollick@gmail.com.