Alan Turing


(Dutch version here)

Alan M. Turing (1912-1954)

Alan Mathison Turing was born June 23th, 1912 in Paddington near London.

Because his father worked until his retirement in 1926 in India, British at the time, he and his older brother grew up in English homes, where expression, originality and creativity were not encouraged at all (so no place for science). Turing however did show interest in the exact sciences and amused himself with chemical experiments.

From 1926 till 1931 he went to an English public school: Sherborne School, where he systematically received bad grades. Only for mathematics and other scientific oriented courses he did better, although his teachers weren't too happy about that either (« His work is dirty »). He was considered more as a problem to society than an added value to it and also in his further life he didn't get the appreciation he really deserved.

In 1931, he obtains a scholarship for King's College, Cambridge. In 1935 he gets a job in Cambridge. In 1936 he receives Smith's Price for his work in probability theory. It seems that he's heading for a successful career as a pure mathematician. His unique mind drives him in another direction.

In 1933 Turing got acquainted with Russel and Whitehead's "Principia Mathematica" and thereby with mathematical logic. Bertrand Russel thought that anything that is mathematically true can be derived with the aid of a well-defined set of derivation rules. But, since then, a lot of questions had arisen: in particular how truth can be caught in a formalism. Then there also was Gödel who had enfeebled Russel's point of view by showing that mathematics is not complete: there exist true theorems about numbers that cannot be proven by a formal application of certain deduction rules.

In 1935 Turing heard, during a lecture of the Cambridge topologue M.H.A. Newman that a similar problem, posed by Hilbert, still wasn't solved. This problem was the question of Decidability, the so called Entscheidungsproblem: does there exist, at least in theory, an algorithm that decides whether a mathematical problem has a solution? If this were true all mathematical problems could be reduced to plain mechanical counting. You could then propose whatever you like and see if after application of a suitable algorithm you've proposed something true or false.

To answer this question you need, first of all, a concise definition of what an algorithm exatly is. Turing provided such a definition.

The Turing machine

A Turing machine is an abstraction, a creation of logic and mathematics. This is extremely vague to serve as an explanation, but we can compare the main concept with some game, for example monopoly. In monopoly we concentrate ourselves on a world where the logic is completely controlled by the rules of the game and we don't care about things happening outside the game. In monoploy you can buy, sell, move your piece etc. The rules don't talk about what do to when your piece gets hungry or falls asleep. That really doesn't matter, does it? A good game is consistent in itself. A Turing machine also is such a closed consistent world. The only habitant of this world is a logical machine.

The machine consists of a finite set of rules, which stay fixed during the calculation process. Furthermore we have a tape of infinite length where information can be saved. The tape is usually divided in cells, that contain exactly one symbol. We also have a read-write-head to show which of the cells should be inspected. The tape contains the information that the machine has to process, it can keep intermediate results and eventually contains the result of the algorithm.

In the example a cell contains binary information: 0, 1 or blanco. The macine is allowed to write over the information and the number of cells that contain information is finite.

The collection rules determines the activity of the head following the tape. A Turing machine can have as many rules as the one who makes her wishes, but the number must be finite. The machine is bounded to follow a certain order: she activates a rule, executes the actions coming with that rule and activates another rule. Before and after the apllication of such a rule the machine finds herself in one of a finite number of states. These states are defined by the one who made the machine.

The machine always knows two things: her present state and de present cell on the tape where the head points to. Those two are the only things the machine needs to know, thanks to her present state and symbol in the cell, she knows what rule to use. Such a rule always says the following:

  1. which symbol to write in the cell, pointed to by the head
  2. move the head one (sometimes none) place to the left or to the right
  3. change the present state in a new state

This is the only way the Turing machine can take care of data. The proces continues until the machine acivates a rule that commands the machine to stop.

A Turing machine is a game where there is no place for any initiative of the player. The only element that may vary is the input tape. As soon as a certain input is known, the machine calls her rules: every input has a execution (or not). Note that a Turing machine can't alter herself. Only the data on the input tape can be changed.

Example

Suppose that 0,1 and blanco are the only symbols and that we have 5 states. State 1 is the beginning state of the machine and when we enter state 5 the machine stops.

Possible rules are the following:

Present state

Present symbol

Write

Move head

New state

1

0

0

Right

2

2

0

0

Right

3

2

1

1

Right

2

3

0

Blanco

Left

5

3

1

0

Left

4

4

0

1

Right

2

The first line says: when your present state is the first state and the head reads 0, overwrite the 0 with a 0 (don't do anything), move the head one place to the right, your new state is state 2.

The Turing machine with these rules, states and appropriate input adds two natural numbers. We use an unary notation for the numbers on the input tape: suppose you want to add two numbers k and x, you must first write a 0, then x ones, a 0, k ones and you end with a 0. (2,3) becomes 01101110.

This Turing machine adds numbers, so when you give it 01101110 as input, the result has to be 0111110

This goes as follows:

number (unary)

Present state

Action

01101110

1

The head points to symbol 0, the present state is 0, so , by the first rule we write a 0 (let the 0 where it is), we move the head one place to the right and enter state 2.

01101110

2

While reading ones you stay in state 2

01101110

2

If you're in state 2 (and reading the first number) and you encounter a 0, this means that you've read the first number and that you may (must) enter state 3.

01101110

3

The intuition is now that all the ones that you encounter now, you should paste to the first ones. You put a 0 wher you are standing, go to the left and alter the state to state 4. We have then 01100110.

01110110

4

Because you're in state 4 en you reads a 0, you write a 1 (this is the one you threw away a minute ago) and you pretend as if you're working with the first number again, i.e. you go back to state 2.

01110110

2

You meet a 0 there (always because you've put it there earlier) and you enter state 3.

01110110

3

Repetition

01110010

4

Repetition

01111010

2

Repetition

01111010

3

Repetition

01111010

4

Repetition

01111100

3

Now you're in state 3, but there is no second number anymore, so you write a blanco over the last 0 and go to the final state, state 5.

0111110

5

The end

There exists a infinite number of more interesting Turing machines, the principles by which it works are always the same. The tape could contain the digits of a number and the machine could have rules to calculate the squareroot of this number.

The real challenge lies in the design of the Turing machine itself: defining the rules and searching the states that will make the machine work as intended.

Also important is the Universal Turing machine, every Turing machine is a bunch of states, rules, inputsymbols,... It's then a clear-cut-case that we can build an Universal Turing machine that has enough rules, states, etc to simulate every Turing machine.

This starts to sound a lot like a computer. On one computer (universal Turing machine) you can run different kinds of software (Turing machines). To process information with a computer is exactly replacing separate symbols according to certain rules. Every task a computer performs can be seen as such a replacement procedure and every task that can not be accomplished by such a replacement procedure can't be programmed for a computer.

We now return to the question that is the origin of those Turing machines: does there exists, for a certain theorem, an algorithm that says whether the theorem is true or false? An algorithm is nothing else than a number of mathematical operations. Turing proves that you can break up those operations into fundamental building blocks. He shows that with Turing machines, you can simulate every possible algorithm (he even hoped that the Turing machine is capable of the things a human brain is capable of- consciousness included)

Checking whether an alghorithm with as input a theorem is true or false, comes then down to checking if a Turing machine with a certain input has a solution or not, so if the Turing machine ends up in an infinite loop. The question is: can we, beforehand, say whether a Turing machine will stop given a certain input? No. We can only say that a Turing machine will stop if it has already stopped (the "halting problem"). Analogue we can say that a theorem is true if there's a proof for it.

Differently put: every calculation that can be mechanically (algorithmically) executed, can be executed by a Turing machine. The other way around, if it can't be executed by a Turing machine then it's not computable.

We'll now see an outline of the proof that Turing had. His theorem is: there doesn't exist a mechanical procedure to see whether a Turing machine stops given a certain input.

It's clear that there infintely many, but a countable number of Turing machines. Therefore we can put all the Turing machines in a infinite sequence: T1, T2,...

Let the result of the n-th machine Tn with input i be Tn(i).

By contradiction:

Suppose that there does exists a rule or procedure to decide whether Tn(i) stops for all values n and i.

Put then all Turing machines with their input and output in a table.

Where there are question matks the Turing machine doesn't stop, we know this by the hypothesis, for example at T1(4). Through some sort of a diagonalisation procedure (cfr. Cantor) we can then make a machine D that always stops for any input. D(i) is :

0 if Ti(i) doesn't stop.
Ti(i)+1 if Ti(i) stops.

But D must then be one of the Ti (because the T's are all the Turing machines). So there's a d for which D = Td. But we've defined D to be different of all Ti . Contradiction.

And so there doesn't exist a procedure to determine whether the Turing machine stops given an input.

As we saw the difficulty doesn't lie in this proof but in effectively building a machine that simulates a given algorithm.

In april 1936 Turing showed his results to Newman, but at the same time the equivalent conclusion of the american logician Church got known, and this robbed Turing of the full reward for his originality. The paper, "On Computable Numbers with an application to the Entscheidungsproblem" had to refer to Church's work and the publication of it was delayed until august 1936. So Church had the same conclusion as Turing for Hilbert's problem, but it was definitely noted that Turing's approach was original and utterly different.

Church depended on assumptions inherent to mathematics, whilst Turing based himself on operations, executable in reality by things or humans. Indeed if you have to prove something about mathematics it could be safer to proof this without using mathematics, this to avoid all kinds of circular reasoning.

Alonzo Church postulated then that there was no more powerful system to perform calculations with than a Turing machine. It certainly is difficult to imagine such a more powerful system, because that system would be able to handle problems that can not even be solved in a structural way. Some propose the human brain as such a system.

If we follow Church and say that the Turing machine is the most powerful system there is then also the brain wouldn't be more powerful and, as a consequence could be simulated by a Turing machine (most people don't like this thought however).

Nevertheless, it stays a fact that such a simple thing as the Turing machine is capable of doing things that any computer nowadays can do - I probably should note that the execution of a task on a Turing machine will be slower. It's nothing but fair that the Turing machine became one of the foundations of modern theory of computers and computability.
In 1938 Turing was offered a temporary post in Princeton, but instead of accepting it he went back to Cambridge. In 1938 en '39 he lived of his function in King's College as a logician and numbertheoretic.

He worked parttime for the British cryptoanalytic department (responsible for decyphering secret messages), the so-called "Government Code and Cypher school". His appointment there fell together with the entry of a scientific approach in the department which was therefore a "on-art-based department". That revolution was mainly a result of the failure of the non-scientific methods to crack the, mechanically generated, Enigma codes, used by Nazi-Gemany.

Almost all German communications where encoded by the Enigma machine. This machine was based on moving rotors, that produced always-changing alfabetic substitutions. The Enigma code was considered to be unbreakable, not even by someone in possesion of the machine.

There was little or no progress in breaking the code until in july 1939 vital information arrived from Polish mathematicians, who were studying the subject for quit a while already.

At the British Declaration of War in september '39 Turing joined the cryproanalytic headquarters in Bletchley Park on a fulltime basis. The Polish method had his limitations in the sense that she was dependent on the Enigma message. Turing made a generalisation of their system that was capable of cracking every Enigma message, if there could be guessed a little piece of the encoded text correctly.

Another Cambridge mathematician W.G. Welchman contributed a bit, but the critical factor was Turing's brilliant mechanisation of subtle logical deductions.

Right : the Enigma machine

When on february the first of 1942 the Enigma machine that encoded the communications between submarines received an extra rotor, panique arose in allied ranks.

A logical weakness in the system solved this and this till the end of the war.

This was all very important in the sense that engineers were forced to invent faster machines. The use of a first decypher machine followed: the "Collosus".

In 1944 Turing was nearly the only one with the following three ideas:

  1. his own concept of the Universal Turing machine
  2. The potential in speed and reliability of the upcoming electronic technology
  3. the inefficiency of developping different machines for different logical processes.

Combined these three ideas provided the idea, the principle, the practical means and the motivation for the modern computer: one single machine capable of executing every programmed task.

Turing himself was very enthousiastic of realising this and he became even more euphoric by a fourth idea: the universal machine would obtain and exhibit de possibilities of the human brain.

After the second World War he worked for the National Physical Laboratory (NPL) and continued his research in computers. He worked on the development of the Automatic Computing Engine (ACE) : one of the first attempts to build a real digital computer. He left the NPL, before the completion of de ACE en moved in 1948 to the university of Manchester where they were working on the Manchester Automatic Digital Machine (MADAM).

Turing could have led the world there and then into software development. Among his studied ideas were the use of mathematical logic to check programs, the implementation of Church's logic calculus on the machine, and other things that combined with his massive knowledge of combinatoric and statistical methods could have set the agenda of computer science for years. He didn't succeed doing this.

Instead a confused period followed, in which Turing wandered between old and new topics. But it's out of this period that the most clear and far-reaching expression of Turing's philosophy about machine and mind came: the paper Computing Machinery and Intelligence which appeared in the philosophical magazineMind in 1950. In this magazine he describes the Turing test (he, of course, called this the "imitation game"), a test to check whether a computer is intelligent or not. This test was en still is a topic of interest in artificial intelligence. The 1987-edition of the Oxford Companion to the Mind describes the test as "the best we have for confirming the presence of intelligence in a machine".

The Turing test :

A person communicates with the computer via a terminal. When the person can't decide whether he's talking with a computer or with a person, then we can say that the computer has all important properties of intelligence. Turing was convinced that such a machine could be build. Check it out yourself at aimovie.warnerbros.com/html/turingTest.html

In the years before his death he worked on something totally different, namely the origin of biological forms: Morphogenesis. As always he made some creditable contributions to this field of science.

But in 1952 Turing got arrested after the police found out that he was having a sexual relationship with a man, a crime in the England of those days. He had the choice between a prison sentence or an hormonal treatment of a year. Turing "chose" for the last option.

The government was aware of the fact that Turing knew about things that had happened during the war (things that would rather be kept secret). And now that Turing wasn't condidered to be "safe" anymore they kept a close eye on him. The contacts Turing had with foreign countries were closely followed with a house-search in March 1953 as a consequence.

Turing got pretty depressed of all this and died on June The 7th in 1954. It's pretty sure that he died by eating a poisoned apple, but whether it was an accident with a chemical experiment or suicide is not known

Sources:

  1. Turing's man by J. David Bolter,The North Carolina University press,1984.

  2. Gödel, Escher,Bach : an Eternal Golden Braid by Douglas R. Hofstadter,Basic Books,1979.
(back to top)
Last modified by stijnh1@yahoo.com on .