Uncomputability in the work of Alan Turing and Roger Penrose

a talk given by Andrew Hodges
for Interface 5, Hamburg, 6 October 2000

This pre-print web-page version has been laid out in three parts: Part 1: Turing from 1936 to 1941 on the first page Part 2: Turing from 1941 to 1954 on the second page Part 3: References and notes on this page.

References

Church A. (1937a) Review of Turing 1936-7. Journal of Symbolic Logic, 2, 42.

Church A. (1937b) Review of Post 1936. Journal of Symbolic Logic, 2, 43.

Church, A. (1940) On the concept of a random sequence, Bull. Amer. Math. Soc. 46, 130-5.

Copeland, B. J. and Proudfoot D. (1996) On Alan Turing's anticipation of connectionism, Synthese, 108, 361-377.
Actual computer simulation of Turing's ideas is described in work of Craig Webster, who also gives an account of Turing's paper with criticisms of Copeland and Proudfoot's analysis.

Copeland. B. J. (1997), The Church-Turing thesis, in E. N. Zalta (ed.), Stanford Encyclopaedia of Philosophy.
This paper fails to cite the primary sources in (Turing 1939) or (Church 1937a). Copeland's main purpose in this paper is to claim there is a sharp distinction between what Church and Turing said, and the thesis that any finitely defined machine has a computable action. He does not seem to have noticed that (Church 1937a) explicitly includes all finitely defined machines in the apparent scope of computability.

Copeland B. J. and Proudfoot D. (1999a) Alan Turing's forgotten ideas in computer science, Scientific American, April 1999.

Copeland B. J. (1999b) A lecture and two radio broadcasts on machine intelligence by Alan Turing, in K. Furukawa, D. Michie. and S. Muggleton (eds.), Machine Intelligence 15, (Oxford: Oxford University Press, 1999)

Davis, M. (2000) The Universal Computer (New York: Norton)
This is a fine account of the emergence of the modern computer as the physical embodiment of a long sequence of ideas (culminating in Turing's ideas), and a much needed corrective to the emphasis often placed on the history of calculating machines as engineered objects. My only regret is that Martin Davis gives the impression that Roger Penrose is unaware of the 'mistakes' argument made by Turing (and of course many others since) in connection with the interpretation of Gödel's theorem. In fact Penrose devotes considerable space to arguing against this position.

Gandy, R. O. (1954) letter to M. H. A. Newman, in the Turing Archive, King's College, Cambridge, to appear in the remaining volume of The Collected Works of A. M. Turing, eds. R. O. Gandy and C. E. M. Yates (Amsterdam: North-Holland)
See the main bibliography on this site for a full description of the Collected Works.

Hodges, A. (1983) Alan Turing: the enigma

Hodges, A. (1997) Turing, a natural philosopher

Newman, M. H. A. (1955) Alan M. Turing, Biographical memoirs of the Royal Society.

Penrose, R. (1989) The emperor's new mind, (Oxford, New York: Oxford University Press)

Penrose, R. (1994) Shadows of the Mind. (Oxford, New York: Oxford University Press)

Penrose, R. (1996) Beyond the doubting of a shadow, http://psyche.csse.monash.edu.au/v2/psyche-2-23-penrose.html

Turing A. M. (1936-7), On computable numbers with an application to the Entscheidungsproblem, see the main bibliography on this site.

Turing A. M. (1939) Systems of Logic defined by Ordinals, see the main bibliography on this site.
This was also Turing's 1938 Ph.D. thesis, Princeton University.

Turing, A. M. (1946) Proposed Electronic Calculator, see the main bibliography on this site.

Turing A. M. (1948) Intelligent machinery, see the main bibliography on this site.

Turing A. M. (1950) Computing machinery and intelligence, see the main bibliography on this site.

Turing A. M. (1951) BBC Radio talk; see the main bibliography on this site.

Turing A.M. (1953/4) Letter to R.O. Gandy, undated, marked by Gandy '1953 or 54.' In the Turing Archive, King's College, Cambridge, section D/4; on-line in the Turing Digital Archive, http://www.turingarchive.org/

Turing, A.M. (1954) Solvable and unsolvable problems, see the main bibliography on this site.