Alan Turing

Being as i am interested in computers and mathematics i have to begin this 'on the shoulders of giants' series with one of the most prolific and influent thinkers of our time: Alan Turing. In this brief essay i'll try to explain how come he singled ed invented the computer, the modern conception of one, by his conceptual thought of the Universal Turing Machine, an abstract device that gived enough time and space could implement any algorithm. The Turing Machine came to be as the conceptual formulation of the modern computer and a powerful instrument in the study of the foundations of mathematics in the footsteps of The Entscheidungsproblem proposed by Hilbert.

When i say that Alan Turing invented the computer i'm not trying to imply that he is the only one who have contributed to the actual invention and construction of the modern computer, i'm only saying that his work on the Turing Machine is at the fundamental level of what is the modern conception of a computer and it would be enough starting from that to actually build one.

One of my heroes, Leibniz, was near achieving that goal, but he missed in linking all his ideas to a coherent and precise definition of a computer. In spite of that, lets not forget that he develop the pascal adding machine into a full calculating device.

Turing's work, besides all is implications in the development of the computer, was also a step further in the achievement reached by Kurt Godel in his famous incompleteness theorem, by stating the foundations of mathematics in terms of the halting problem, meaning that no turing machine could decide if all programs halt or not and consequently any system of formal logic is incomplete if coherent. More recently Gregory Chaitin stated the halting problem in terms of the probability that a program halts and reached the perturbant conclusion that even at a fundamental level of mathematics as in algebra there are mathematical facts that are unproven unless we take them has an axiom; they are uncompressable truths with maximum entropy or randomness.

The Entscheidungsproblem mentioned above, question whether there exists a definite method which, at least in principle, can be applied to a given proposition to decide whether that proposition is provable. Turing's great insight in his 1936 paper 'On computable numbers, with an application to the Entscheidungsproblem' was to perceive Hilbert's question in terms not of proofs, but of computing numbers. As his title said, the Entscheidungsproblem was only an application of a new idea, that of computability.

His paper starts by asking how can we specify the infinite in finite terms? In particular, how can we specify the infinite sequence of digits in a 'real number', such as n = 3. 141592, 653...? What does it mean to say that there is a definite method for calculating such a number? Turing's answer lies in defining the concept of the Turing machine.

How Turing got his result? He use'd a version of Cantor's diagonal method from set theory. He first defined a turing machine as a device capable of a very simple set of operations gived by a 'table of behavior', each one being a specific turing machine, and in some state unequivocally gived by it's current configuration plus the symbol scanned on tape. (more details)Then he defines a computable number as an infinity sequence of symbols that can be printed on a turing machine starting with a blank tape. He then rationalizes that if we order all the turing machines in a sequence we can obtain a number that differs in the Nth digit of the Nth turing machine - the diagonal method - so it's uncomputable. But if it can be defined how is it uncomputable? The problem lies in knowing if a turing machine actually produce an infinite number; Turing prove that there is no turing machine which can be applied to another turing machine proving that it will ever produce an infinite number, so that the problem itself - know known as the halting problem - is not computable. Turing states that if there was such a machine it could be applied to itself raising a contradiction - another instance of the self referencing problem finded in Godel's proof and Russel's paradox. So the question of defining something to which that is no mechanical procedure to solve it can be easily translated to an abstract mathematical question and formal logic and therefore to give a negative answer to Hilbert's Entscheidungsproblem.

The Universal Turing Machine

Besides given a definitive answer to the Entscheidungsproblem and defining the field of computability in new terms Turing's work had a practical implication: it laid out the principle of the computer through the concept of the universal Turing machine.

Given that there is a mechanical procedure capable of implementing any 'table of behaviour' in a Turing machine then there is also a more abstract one capable of implementing any Turing machine, what Turing called a Universal Turing Machine.

Today we can not but associate Turing original ideas with the concept of the modern computer. It's easy to correlate the universal Turing machine, a specific Turing machine and is configurations respectively with the computer, a computer program and the instruction blocks of a computer program. Turing also gave an algorithmic view of computation applied to the human mind which makes him also a prominent thinker in the philosophy of mind, because in spite of his pioneer work in the development of the concept of the computer, the subject of his study was the human brain as a start point from which would eventually emerge a computer.

Starting with Godel's proof of incompleteness and Alonzo Church lambda calculus we already had the answers to the questions Turing set to solve in his own work at the time he published his results, but the novel approach he devised was so ingenious and new that he achieved the conception and definition of the computer on paper before it would be physically implemented so that we might even say that he invented it.

World War II

The advent of the World War II had a profound impact in Turing´s live. Earlier, he developed an interest and some ideas about codes, cyphers and the global field of cryptanalysis. Armed with that skills he naturally achieve a position in UK effort to break German codes and their Enigma machine at Bletcheley Park. This also related with his previous experience in constructing computers: at Princeton he spent time in building a machine out of electromagnetic relays which effected binary multiplication as an encoding device, with some theory of immunity to cryptanalysis. When back at Cambridge, Turing also designed and partially built another machine, which approximated by gear-wheel motion a Fourier series for the Riemann zeta-function. It was intended to shorten the hard labor of finding the possible locations of zeros - the subject of the Riemann hypothesis, which remains today perhaps the most important unsolved problem in mathematics.



In Bletcheley Park he participated in the design of a machine called 'the Bombe' and had direct contact with the Colossus which was used in breaking the german Enigma successor, the Lorenz cipher. Due to the classified nature of his war effort to reengenering german ciphers and codes, that facet of his life was keeped secret until much after the war ended. But we can now recognize the great impact of that work simultaneous in the war outcome and to the evolution, use and recognition of the intrinsic advantages of electronic computers as a tool to solve problems.



Post War

Following his war experience, Turing went to the National Physical Laboratory and worked on his detailed design for a computer, submitting it for approval in March 1946. Turing's Automatic Computing Engine (ACE), as it was dubbed was chronologically second to the June 1945 EDVAC report bearing von Neumann's name, but in addition to the originality of its hardware design, it was ideologically independent: for (i) it was conceived from the outset as a universal machine for which arithmetic would be just one application, and (ii) Turing sketched a theory of programming, in which instructions could be manipulated as well as data, a foresight vision of the metaprograming approach.

This is also related with Turing later interest in machine intelligence and learning in the broad field of Artificial Intelligence. In Manchester, where he got his first full academic post, he and the small group around him published articles under the heading 'Digital computers applied to games' in 1953, which mark pioneering research into machine intelligence. But this lead made no impact on the fresh start to artificial intelligence made by Newell, Simon, Minsky and McCarthy in the United States. Nevertheless in his famous 1950 paper 'Computing machinery and intelligence' he presents the idea of an 'imitation game' also known as the Turing test, in which a human has to interact with 'someone' in a closer room through a teletype device and tell if it is a human. Turing says that if a machine can play the human role well, it can elude his human interactor in thinking his talking to a human rather a machine, then the machine must exhibit intelligence behavior, human intelligence. Turing predicts that by the final of 20th century we should be able to construct such a machine, a bold assumption that we are yet to achieve.

Nevertheless much of his other contributions to philosophy, logic, mathematics, and the emergent field of computation provided invaluable tools of thought that enable us to progress the state of civilization and maybe, in the proper time, the fulfillment of his vision about computers, intelligence and their expression in an artificial intelligence synthesis and in doing so perhaps we be able to know a little more about ourselfs and answer the primordial philosophical question about who we are.