 Philosophy Area |
The Great Philosophers See the Alan Turing Home Page for a guide to this website. |
Part 3 of Turing: a natural philosopher (1997)
Church's Thesis and Turing's Thesis
This was a triumph for anyone, let alone an isolated graduate of 23, but Turing suffered an immediate setback in a tiresomely classic case of scientific coincidence. Before he had submitted his paper, Alonzo Church, the pre-eminent American logician at Princeton, announced the same conclusion regarding the Entscheidungsproblem. Turing took the time until August 1936 to write an appendix relating his result to Church's. For publication by the London Mathematical Society, Newman had to make a case that Turing's argument was different from that produced by Church. In fact Turing's argument differed from Church's in a fundamental way. When the dust had settled, in 1938, he gave his own view in the self-effacing terms that in public he always used of his own work:A function is said to be 'effectively calculable' if its values can be found by some purely mechanical process. Although it is fairly easy to get an intuitive grasp of this idea, it is nevertheless desirable to have some more definite, mathematically expressible definition. Such a definition was first given by Gödel at Princeton in 1934... These functions were described as 'general recursive' by Gödel... Another definition of effective calculability has been given by Church... who identifies it with lambda-definability. The author [i.e. Turing himself] has recently suggested a definition corresponding more closely to the intuitive idea... It was stated above that 'a function is effectively calculable if its values can be found by a purely mechanical process.' We may take this statement literally, understanding by a purely mechanical process one which could be carried out by a machine... The development of these ideas leads to the author's definition of a computable function, and to an identification of computability [in Turing's precise technical sense] with effective calculability. It is not difficult, though somewhat laborious, to prove that these three definitions are equivalent. [4]Turing here gives a view on what is now known and famous as Church's thesis. Although Church's thesis is nowadays given various other interpretations, in 1936 it was the claim that effective calculability could be identified with the operations of Church's very elegant and surprising formalism, that of the lambda-calculus. As such it lay within the world of mathematical formalism. But Turing offers a reason why Church's thesis should be true, drawing on ideas external to mathematics, such as that one cannot do see or choose between more than a finite number of things at one time. Church's thesis is now sometimes called the Church-Turing thesis, but the Turing thesis is different, bringing the physical world into the picture with a claim of what can be done. It should not go without mention that Turing after referring to his machine definition of computability, also cited the work of the Polish-American logician Emil Post, which had also brought an idea of physical action into computation. However Post had not developed his ideas so fully.
The universal Turing machine
Since the modern digital computer is now so important to the exploration of Turing's ideas, a digression is called for to explain its relationship to this paper. It is a startling fact that On Computable Numbers not only solved a major outstanding question posed by Hilbert, opened the new mathematical field of computability, and offered a new analysis of mental activity, but had a practical implication: it laid out the principle of the computer through the concept of the Universal Turing machine.The idea of the Universal machine is easily indicated. Once the specification of any Turing machine is given as a table of behaviour, tracing the operation of that machine becomes a mechanical matter of looking up entries in the table. Because it is mechanical, a Turing machine can do it: that is, a single Turing machine may be designed to have the property that, when supplied with the table of behaviour of another Turing machine, it will do what that other Turing machine would have done. Turing called such a machine the Universal machine. A technical problem arises in encoding the table in a linear form for the 'tape' and arranging working space, but these are details.
Turing introduced the universal machine as a tool in the argument described above for exhibiting an uncomputable number. As such it was not necessary to his conclusion regarding the Entscheidungsproblem. But Turing made the very striking concept prominent in his paper, and according to Newman's later statement, was inspired even then to consider practical construction. It is the Universal machine which gives Turing the claim to have invented the principle of the computer — and not merely in abstract principle, as we shall see. And nowadays it is impossible to study Turing machines without thinking of them as computer programs, with the universal machine as the computer on which the programs are run. It is not difficult to turn a 'table of behaviour' into the explicit form of a modern program, in which each 'configuration' becomes a numbered instruction, containing IF conditions which dictate a writing action and the number of the next instruction.
Some care is needed here with terminology. The phrase 'the Turing machine' is analogous to 'the printed book' in referring to a class of potentially infinitely many examples. Within this class, certain Turing machines are 'universal', having sufficient complexity to interpret and execute the table of behaviour of any other Turing machine. Again, although we speak of 'the' universal Turing machine, there are infinitely many designs with this property.
Turing's own paperwork in constructing tables of behaviour must have put him in the mind of a programmer; all the more so as Turing used abbreviated notation which amounts to defining subroutines. The mind of the programmer cannot be said to originate with Turing's paper; the axiomatic programme, and Gödel's ingenious methods, had already given rise to this way of thinking. But in Turing's work the idea is formalised in the language of instruction, to a degree that it is hard to believe that the computer was not already in existence. Yet the point should be emphasised: Turing was not considering the computing machines of his day. He was modelling the action of human minds. The physical machines would come ten years later.
[4] Systems of logic based on ordinals, Proc. Lond. Math. Soc
(2) 45 pp 161-228 (1939).
This was also Turing's Princeton Ph.D. thesis (1938). (See also the Bibliography on this site.)
© 1997, Andrew Hodges.
CONTINUE to part 4
Book index | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
| Quick Links: |
|
|
|
|
|
|
|
| |||||
