A Thesis and an AntithesisThe origin of my article lies in the appearance of Copeland and Proudfoot's feature article in Scientific American, April 1999. This preposterous paper, as described on another page, suggested that Turing was the prophet of 'hypercomputation'. In their references, the authors listed Copeland's entry on 'The Church-Turing thesis' in the Stanford Encyclopedia. In the summer of 1999, I circulated an open letter criticising the Scientific American article. I included criticism of this Encyclopedia entry. This was forwarded (by Prof. Sol Feferman) to Prof. Ed Zalta, editor of the Encyclopedia, and after some discussion he invited me to submit an entry on 'Alan Turing.'
My entry, which appeared in 2002, stands on its own as a discussion of Turing's life and thought, but it is also constructed as a corrective to Copeland's arguments. Whether anyone has ever noticed this I do not know, as the editors did not wish to see contributors' differences accentuated and they would probably escape any but a really expert reader. The point of this introduction is to highlight those differences. You can then read and judge for yourself.
Copeland's entry is focussed on the claim that the Church-Turing thesis was never meant to apply to machines. It was a thesis ONLY about what a human being, working to a rule, could do. The thesis that anything a machine can do is computable, is called 'Thesis M' (following the logician Robin Gandy, who first discussed this distinction). So he is adamant that we should never interpret Church or Turing as stating Thesis M.
Copeland's argument comes to a crunch when he writes, near the end of the article,
... when Church writes (in a review of Post (1936)):To define effectiveness as computability by an arbitrary machine, subject to restrictions of finiteness, would seem to be an adequate representation of the ordinary notion (Church 1937b: 43),he is to be understood not as entertaining some form of thesis M but as endorsing the identification of the effectively calculable functions with those functions that can be calculated by an arbitrary machine whose principles of operation are such as to mimic the actions of a human computer.
This is nonsense. Church was enthusiastically entertaining some form of Thesis M. On the facing page of the Journal of Symbolic Logic is Church's review of Turing's paper, which of course hardly anyone in 1937 knew about. Church introduced the new concept of Turing machine thus:
The author [i.e. Turing] proposes as a criterion that an infinite sequence of digits 0 and 1 be "computable" that it shall be possible to devise a computing machine, occupying a finite space and with working parts of finite size, which will write down the sequence to any desired number of terms if allowed to run for a sufficiently long time. As a matter of convenience, certain further restrictions are imposed on the character of the machine, but these are of such a nature as obviously to cause no loss of generality — in particular, a human calculator, provided with pencil and paper and explicit instructions, can be regarded as a kind of Turing machine.You can see immediately that Church didn't say that the machine must be of a kind configured to mimic a human computer. On the contrary, he referred to the human calculator as a special case of the wider class of finitely defined 'machines'. What Copeland assures us Church was 'endorsing' is his wishful thinking. In any case the expression 'arbitrary machine' obviously means 'any machine whatever'. Copeland tries to explain this by saying that the Turing machine has 'arbitrary' aspects to its technical definition, but this is simply not what Church's words mean. If there were any doubt about their meaning, it would be dispelled by the paragraph I have quoted. Church characterised the scope of the Turing machine as being the scope of all finitely defined computing machines. This is just Thesis M.
Church wrote this characterisation in Princeton in 1937 while Turing was there with him; he repeated it in 1940; Church was famous for making very careful and precise statements of everything; there's no reason whatever to think that Turing and Church were at odds over this.
The only way that Church's statement differs from 'Thesis M' is that it isn't presented as an important thesis, something that needed to be argued for and defended against possible objections. It reads as if he thought it perfectly obvious that Turing's definition could encompass anything you could call a machine. This is not surprising, given that the first really non-trivial machines only got going in 1940 (this is Turing's own historical comment in 1948, an allusion to his secret Bombes.)
Why then was Turing's 1936 definition of computability made very much in terms of what a human calculator, working to a rule, could do? There are two obvious reasons: (1) Hilbert's Entscheidungsproblem, which Turing was addressing, is posed in terms of what human mathematicians can do and (2) in 1936, human beings could perform far more complicated tasks than any known machine, so that Turing's definition makes for the sharpest possible criterion of 'mechanical process'.
There are a number of other distortions in Copeland's article, all in the cause of claiming that Turing was maintaining this clear distinction between what he said and 'Thesis M'. For example, in an earlier section, when describing what Turing proved with the aid of the Turing machine concept, Copeland writes that this doesn't say anything about what a machine might do because
For among a machine's repertoire of atomic operations there may be those that no human being unaided by machinery can perform.which introduces an idea completely absent from Turing's writing, that of machines with superhuman powers embodied in their basic operations. A reader might mistake this for being a paraphrase of Turing's own arguments. In fact this is just the reverse of Turing's concern, which was with whether machines had a hope of doing as much as what human beings do. I have tried in my own article to supply an antidote to all this. Since Copeland is primarily concerned here with the question of what Turing thought 'a machine' could be, it's odd that he makes no reference to the extended analysis of the concept of 'machine' that Turing gave in 1948. Turing did then broaden the concept to include for instance 'continuous' as opposed to 'discrete' machines. But there is no reference to the idea of machines with atomic operations no human being could perform, or of machines managing to go beyond computable functions. In this case you can see for yourself on-line: here is a scan of the original Turing typescript in the Turing Digital Archive.
Does it matter?Copeland makes a great deal of the sins of various prominent writers in misrepresenting the Church-Turing thesis. In some cases I am sure he is right: I have no idea where David Deutsch's 'Turing Principle' is meant to be found in Turing's work. But others, writing with unguarded generality about 'machines,' are hardly different in spirit from Church himself. For those concerned with the historical foundations of the cognitive sciences, these questions are probably still very important.
On the other hand, there is a limit to the significance of purely historical questions of what Church and Turing said or thought. Church could simply turn out to be wrong in his rather simplistic assumption about machines. He clearly could not have thought about the nature of the physical world as it is investigated today — black holes, superstrings, the lot. Church and Turing could hardly be blamed if their perception of the physical world in 1937 was rendered obsolete by new discovery. Science moves on, and sometimes the greatest figures are left behind. But Copeland apparently wants to adhere to two things: (1) Church's thesis and (2) the possibility of 'hypercomputing': physical systems that have machine-like properties but are not computable. The only way to reconcile these two things is to hold that Church's thesis was never meant to apply to machines, only to people. This assertion of Copeland is now often cited by other people, and has become part of philosophical lore. But it is not consistent with the record.
Proceed to my Stanford Encyclopedia entry on 'Alan Turing'
Compare with Copeland's entry on 'The Church-Turing Thesis'