Alan Turing and the Enigma of Computability

Artzia.comHistoryBiographyTuring :
byAR
Alan Mathison Turing, b. June 23, 1912, d. June 7, 1954, was a British mathematician who conceived of a machine that could compute by reading and writing an infinite tape according to some simple instructions and state transitions. From this he was able to show the existence of uncomputable functions. For example, no program can determine if any arbitrary program will terminate. He played a significant rôle in cracking German codes duringWorld War II, and proposed a test for machineintelligence.
He went toKing‘s College, Cambridge in 1931 to readMathematics. Turing graduated from Cambridge in Mathematics in 1934, and was a fellow at Kings for two years, during which he wrote his now famous paper published in 1937, On Computable Numbers, with an Application to the Entscheidungsproblem. In it, he proposed a machine that could move from one state to another by following a rigorous set of rules. From this he was able to show the existence of uncomputable functions. For example, no program can determine if any arbitrary program will terminate. This led to a computing scheme that foreshadowed the logic of digitalcomputers.
Consistency, Completeness, and Computability
With the ever-increasing abstraction of mathematics away from Euclidean ‘reality‘, mathematicians wanted a way to be sure their work was sound. In particular, they wanted to be sure there were no internal inconsistencies, such that if you had proven a theorem T to be true, then you could be absolutely sure that nobody would ever prove the opposite. If they could, then anything could be proven, and the whole system would become meaningless. They also wanted to be able to guarantee the completeness of their systems, which meant that if there was a theorem T in it, then there would be a way to prove or disprove it. For any specific theorem (e.g. Fermat‘s Last Theorem) it might be extremely difficult to do, but still, mathematicians were confident that in principle, every theorem in a system could be proven or disproven.
UntilKurt G鰀el came along. He showed that in a formal axiomatic system, you cannot have both consistency and completeness; either you cannot prove everything in the system, or you could not (within the system) guarantee that there could not be any contradictions. This came as a major shock to mathematicians.
G鰀el had shown that any sufficiently rich mathematical axiom system is incomplete in that there must exist propositions whose truth can never be determined (undecidable propositions within the system).
Turing graduated in 1934 then, in the spring of 1935, he attendedMax Newman‘s advanced course on the foundations of mathematics. This course studied G鰀el‘s incompleteness results andHilbert‘s question on decidability: given a mathematical proposition could one find an algorithm which would decide if the proposition was true of false? Turing was motivated by G鰀el‘s work to seek an algorithmic method of determining whether any given propositions were undecidable, with the ultimate goal of eliminating them from mathematics.
Instead, he proved in his seminal paper On Computable Numbers, with an Application to the Entscheidungsproblem (1936), that there cannot exist any such universal method of determination and, hence, that mathematics will always contain undecidable (as opposed to unknown) propositions.
An Outline of Turing‘s Computability Proof
In September 1936 Turing went to theInstitute of Advanced Studies atPrinceton, completing a Ph.D. (1938) under the direction of the American mathematicianAlonzo Church. He then returned to England and accepted a renewed fellowship at King‘s College.
World War 2: The Enigma Codes
During World War 2, Turing worked in the British Foreign Office, where he played a leading role in efforts to break enemy codes.
Armed forces have always been dependent on communications. The efficiency of Germany‘s armed forces in the second world war was only made possible by the use of radio communications. Messages sent this way had to be enciphered, and the encryption system they used was developed from one that was commercially available before the war. This was then modified in such a way as to significantly increase the difficulty in breaking it. These Enigma machines could generate over 1 trillion different coding patterns. The Germans believed they were too sophisticated for Allied forces to break them. But in one of the best-kept secrets of the war, first the Poles, and later the British and Americans succeeded in deciphering messages.
During World War II (1939-1945), Turing served with the British "Government Communication Headquarters" (GCHQ) atBletchley Park, where he played a significant role in breaking the German "Enigma" codes. There he used a machine called Collossus to decipher the Enigma codes. These machines were the predessors to the first digital computers.
He was in the first handful of able mathematicians drafted into their code-breaking operations. In the next three years Turing was the key figure in the continual battle to decode messages encrypted by the increasingly complex Enigma machines, using the Bombe machine.

The wooden device in the foreground is a 4 rotor German Enigma machine, used for encoding. The large machine in the background is a "Bombe," used for breaking the code. Working out the details of codebreaking machines was one of the developments that fostered electronic computers. Smithsonian Photo by Laurie Minor-Penland.
The Bombe was an electro-mechanical device, developed by Turing with help from another mathematician W. G. Welchman, inspired by the Polish ‘Bomba‘. Many of Germany‘s secret messages could be deciphered and read whith it. The periods when the Naval code could be broken saw dramatic reductions in the shipping losses from the Atlantic convoys so essential to the conduct of the Allied war effort. The importance of this for the development of WWII can hardly be underestimated. The allies could always be one step ahead and avoid the worst consequences of for example the submarine war. The British brought the Americans into the picture during the war, and the Americans furnished many of the resources to attack ever more complex versions of the Enigma, especially the naval Enigma, when British resources began to run thin. Information from the decrypted messages was used by the Allies time after time to outmaneuver German armies.
He later worked on the development of an electronic computer, on theories of artificial intelligence, and on the application of mathematical theory to biological forms. Alan Turing‘s research has had profound influence on logic,computability, moderncomputers, and machine intelligence.
The Turing Test
After the War Turing went on to work for the National Physical Laboratory (NPL), to lead the design, construction, and use of a large electronic digital computer called the Automatic Computing Engine (ACE).
Turing left the (NPL) and moved to the University of Manchester, to become deputy director of the Computing Laboratory, where he wrote programs for the Manchester Automatic Digital Machine (MADAM), the computer with the largest memory capacity in the world at that time.
Meanwhile Turing began to think about the relationship between computers and the mind. He championed the theory that computers eventually could be constructed that would be capable of mimicking human thought. I Think, Therefore, I Am Named after the famous French philosopher and mathematician Rene DesCartes, RENE is a language used for artificial intelligence. The language is being developed at the Chicago Center of Machine Politics and Programming under a grant from the Jane Byrne Victory Fund. A spokesman described the language as "Just as great as dis [sic] city of ours." The center is very pleased with progress to date. They say they have almost succeeded in getting a VAX to think. However, sources inside the organization say that each time the machine fails to think it ceases to exist.
In 1950 he produced a paper on "Computing Machinery And Intelligence"; he invented a test that he said would prove a machine could think. This test later became known as the Turing Test. Turing was convinced that if a computer could do all mathematical operations, it could also do anything a person can do, a still highly controversial opinion. To argue for this position a criterion of intelligence was needed. Turing expressed this criterion as a test.
The Turing Test has a computer and a person with the interrorgator trying to distinguish which is the computer. The interrorgator asks questions via teletype so no visual identification can be made. The test is repeated with a range of people in the human position and if the number of times that repeated identification is less than pure guesswork then the machine has passed.
When the person is unable to decide whether he is talking to a computer or another person, the computer can safely be said to possess all important characteristics of intelligence. Turing was convinced that is was possible to build such a machine.
Turing Test Q: Please write me a sonnnet on the subject of the Forth Bridge. A: Count me out on this one. I never could write poetry. Q: Add 34957 to 70764 A: (Pause aobut 30 seconds and then give as answer) 105621. Q: Do you play chess ? A: Yes. Q: I have K at my K1, and no other pieces. You have only K at K6 and R at R1. It is your move. What do you play? A: (After a puase of 15 seconds) R-R8 mate.
Turing believed that thinking machines could be created by the year 2000. He was too optimisitic. In it‘s modern form the test is conducted in a competition called The Loebner Prize.
Alan Turing‘s paper was such a revolutionary piece of work because the digital computer was still very much in in it‘s infancy. It probably wasn‘t until 1990 when a computer came anywhere near passing the test, and to this day no computer ever has.
Turing‘s papers on the subject are widely acknowledged as the foundation of research in artificial intelligence.
In 1945 Turing was awarded the O.B.E. for his vital contribution to the war effort. In 1951 Turing was elected a Fellow of the Royal Society. He was still doing research on computers when in 1952 a friend of his lover broke into his house. In the following police investigation he openly mentioned his homosexuality. It turned out that the police were more interested in the fact that he was gay than in the actual crime, since being gay was a crime in Britain at the time. Turing was charged and sentenced to hormonal treatment with estrogen.
In later years Turing was professionally hindered by his 1952 arrest for violation of British homosexuality statutes. The depression he went through following the conviction was probably the main cause of his suicide in 1954 at the age of 41. He killed himself by eating an apple soaked in potassium cyanide. Breaking the Code (1987), a play by Hugh Whitemore, is based on his life.
More on Alan_Turing
Alan Mathison Turing (June 23, 1912 - June 7, 1954) was a British mathematician and cryptographer, and is considered to be one of the fathers of modern computer science. He provided an influential formalisation of the concept of algorithm and computation: the Turing machine. He formulated the now widely accepted ‘Turing‘ version of the Church-Turing thesis, namely that any practical computing model has either the equivalent or a subset of the capabilities of a Turing machine. During World War II he was the director of the Naval Enigma Hut at Bletchley Park for some time and remained throughout the War the chief cryptanalyst for the Naval Enigma effort. After the war, he designed one of the earliest electronic programmable digital computers at the National Physical Laboratory and, shortly thereafter, actually built another early machine at the University of Manchester. He also, amongst many other things, made significant and characteristically provocative contributions to the discussion "Can machines think?"