 My Publications |
Machines and Oracles: comment by Andrew Hodges |
Did Church and Turing have a thesis about machines?
by Andrew Hodges
for Church's Thesis after 70 years, ed. Adam Olszewski (2006)
This article is made available in .pdf form to be downloaded here.
Copeland and Proudfoot's article in Scientific American, April 1999:
comment by Andrew Hodges
In April 1999 I read with amazement an article in the popular magazine Scientific American by the New Zealand philosophers B. J. Copeland and Diane Proudfoot, entitled 'Alan Turing's Forgotten Ideas in Computer Science,'
and advertised on the cover as 'The Lost Brainstorms of Alan Turing.'
The authors put forward two areas of 'forgotten ideas'. One of these was that of Turing's 1948 proposals for developing networks of unorganised elements, which could be said to anticipate the neural network or 'connectionist' approach to Artificial Intelligence. Here they had found a topic of genuine interest to air, although their discussion is not beyond criticism.
Turing in the land of NZ
The other supposedly 'forgotten idea', however, was that of the 'oracle' in Turing's 1938-9 paper Systems of logic based on ordinals. Specific ideas were proposed about how this could 'work' in a physical implementation. The proposition that the authors featured as part of an explanation of what 'Turing did imagine' was this: that it might be possible to measure a physical quantity such as the 'amount of electricity' in an electrical capacitor to infinite precision. If the quantity thus measured was an uncomputable number, it would serve as an oracle. If the uncomputable number happened to be one associated with the Halting Problem for Turing machines, then a famously uncomputable problem would become soluble.
 | This is the picture offered by Copeland and Proudfoot of the oracle, storing an infinite and uncomputable string of 0's and 1's. |
April Fool?
This must surely be the most ludicrous proposal ever aired in Scientific American. At first I wondered if it was an April Fool.What do the authors mean by 'an exact amount of electricity?' If it means counting electric charges, then any measurement will give an integer, not an uncomputable number. If on the other hand they mean some classical measurement of a continuous variable, then they are ignoring the nature of matter. A macroscopic object like a capacitor is not even defined with much precision, let alone measurable to infinite precision. It is like asking for the exact width of a cloud. Even at zero temperature, its constituent particles are quantum-mechanical wave-functions, involving superpositions of position, momentum and spin. A classical measurement cannot be related precisely to these. Further, general relativity tells us that the geometry of the space in which the object exists, is itself fluctuating in a way that depends on every particle in the universe, and this fluctuation affects all measurements. Standard physical theory would also imply that no measurement can be made to made to a precision involving distances below the Planck length, 10–33 cm., because space-time geometry itself is in some kind of quantum fluctuation at this level. Far from being deterred by the Planck scale, Copeland and Proudfoot go on to illustrate making a measurement to an accuracy of one part in 28735439. Even this, however, is nothing compared with their demand for infinite precision. Note that the infinite precision is absolutely essential to their argument because any uncomputable number can be approximated as closely as desired by a computable number.
This kind of discussion would only be meaningful in a hypothetical or 'toy' universe, used for the sake of logical argument, where infinite-precision measurements could be made. But even in such a fictional world, it is hard to see why any physical object should have a property which happens to agree precisely with the infinite slew of answers to the Halting problem as defined in one particular, arbitrary, conventional coding of Turing machines. And how could such a thing, even if true, ever be verified?
But Copeland and Proudfoot were not describing a 'toy' universe; they claimed that 'the search is under way' in the real world to find an oracle that could revolutionise computer science. Dear readers, I do not advise investing all your money on the basis of this prospectus.
Travesty of Turing
I was appalled that this hare-brained idea should be associated with Alan Turing as his 'lost brainstorm.' Scientific American said (see its webpage) that this 'hypercomputation' is a 'hot idea' which Alan Turing had 'anticipated in detail.' I suspect many people with a physical or engineering background took it, on reading this nonsense, that Turing had come up with this ridiculous idea because he was an impractical logician without understanding of reality. What a slur on his reputation! Turing could be impractical with details of electronic circuits, but had an excellent grasp of how logical ideas were embodied in engineering: it was central to his Second World War contribution as well as his 1945 computer plan. (See for instance his report on the American-engineered Bombes on this Turing Internet Scrapbook page.) Turing proposed nothing resembling this impossible contraption.The suppressed citation
Amazingly, the authors' list of citations failed to include Turing's paper! They never mentioned that it was published by the London Mathematical Society in 1939, and included by Martin Davis in his collection of classic papers The Undecidable in 1965, in print ever since and available from Amazon now. Instead, Copeland and Proudfoot referred to it only as being Turing's 1938 Ph.D. thesis, leaving the impression that it was an unpublished work only recently discovered by the authors. In any case readers were denied the chance to see for themselves what Turing had actually written.The reality
In fact, the whole point of Turing's oracle is that it describes a non-mechanical logical element. There is more comment in the introduction to my entry in the Stanford Encyclopedia of Philosophy.| Quick Links: |
|
|
|
|
|
| |||