A myth has arisen concerning Turing's article of 1936, namely that Turing set forth a fundamental principle concerning the limits of what can be computed by machine—a myth that has passed into cognitive science and the philosophy of minds to wide and pernicious effect. This supposed principle, sometimes incorrectly termed the Church-Turing thesis, is the claim that the class of functions that can be computed by machines is identical to the class of functions that can be computed by Turing machines. In point of fact, Turing himself nowhere endorses or even states this claim (nor does Church). The author describes a number of notional machines, both analog and digital, that can compute more than a universal Turing machine. These machines are exemplars of the class of nonclassical computing machines. Nothing known at present rules out the possibility that machines in this class will one day be built or that the brain itself is such a machine. These theoretical considerations undercut a number of foundational arguments that are commonly rehearsed in cognitive science and gesture toward a new class of cognitive models.
Get full access to this article
View all access options for this article.
References
1.
Aberth, O. (1968). Analysis in the computable number field. Journal of the Association of Computing Machinery, 15, 275-299.
2.
Boden, M. A. (1988). Computer models of mind. Cambridge, UK: Cambridge University Press.
3.
Bush, V. (1931). The differential analyser: A new machine for solving differential equations. Journal of the Franklin Institute, 212, 447-488.
4.
Bush, V. (1936). Instrumental analysis. Bulletin of the American Mathematical Society, 42, 649-669.
5.
Bush, V. , & Caldwell, S. H. (1945). A new type of differential analyser. Journal of the Franklin Institute, 240, 255-326.
6.
Chalmers, D. J. (1996). The conscious mind: In search of a fundamental theory. New York: Oxford University Press.
7.
Church, A. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics, 58, 345-363.
8.
Churchland, P. M. , & Churchland, P. S. (1990). Could a machine think?Scientific American, 262, 26-31.
9.
Copeland, B. J. (1993a). Artificial intelligence: A philosophical introduction. Oxford, UK: Basil Blackwell.
10.
Copeland, B. J. (1993b). The curious case of the Chinese gym. Synthese, 95, 173-186.
11.
Copeland, B. J. (1996). What is computation?Synthese, 108, 335-359.
12.
Copeland, B. J. (in press-a). Accelerated Turing machines.
13.
Copeland, B. J. (in press-b). Turing's O-machines, Searle, Penrose, and the brain.
14.
Copeland, B. J. (in press-c). What is the Church-Turing thesis?
15.
Copeland, B. J. , & Proudfoot, D. (1996). On Alan Turing's anticipation of connectionism. Synthese, 108, 361-377.
16.
Copeland, B. J., & Sylvan, R. (in press). Computability: A heretical approach.
17.
da Costa, N.C.A. , & Doria, F. A. (1991). Classical physics and Penrose's thesis. Foundations of Physics Letters, 4, 363-373.
18.
Dennett, D. C. (1978). Brainstorms: Philosophical essays on mind and psychology. Brighton, UK: Harvester.
19.
Dennett, D. C. (1991). Consciousness explained. Boston: Little, Brown.
20.
Deutsch, D. (1985). Quantum theory, the Church-Turing principle and the universal quantum computer. Proceedings of the Royal Society, Series A, 400, 97-117.
21.
Doyle, J. (1982). What is Church's thesis? An outline. Laboratory for Computer Science, MIT.
22.
Dreyfus, H. L. (1992). What computers still can't do: A critique of artificial reason. Cambridge: MIT Press.
23.
Fodor, J. A. (1981). The mind-body problem. Scientific American, 244, 124-132.
24.
Fodor, J. A. (1983). The modularity of mind. Cambridge: MIT Press.
25.
Gandy, R. (1980). Church's thesis and principles for mechanisms. In J. Barwise, H. J. Keisler, & K. Kunen (Eds.), The Kleene Symposium (pp. 123-148). Amsterdam: North Holland.
26.
Gandy, R. (1988). The confluence of ideas in 1936. In R. Herken (Ed.), The universal Turing machine: A half-century survey (pp. 55-111). Oxford, UK: Oxford University Press.
27.
Garzon, M. , & Franklin, S. (1989). Neural computability: II. Abstract. Proceedings of the IJCNN International Joint Conference on Neural Networks, 1, 631-637.
28.
Geroch, R. , & Hartle, J. B. (1986). Computability and physical theories. Foundations of Physics, 16, 533-550.
29.
Gregory, R. L. (1987). The Oxford companion to the mind. Oxford, UK: Oxford University Press.
30.
Guttenplan, S. (1994). A companion to the philosophy of mind. Oxford, UK: Basil Blackwell.
31.
Haugeland, J. (1985). Artificial intelligence: The very idea. Cambridge: MIT Press.
32.
Hofstadter, D. R. (1980). Gödel, Escher, Bach: An eternal golden braid. London: Penguin.
33.
Johnson-Laird, P. (1987). How could consciousness arise from the computations of the brain? In C. Blakemore & S. Greenfield (Eds.), Mindwaves (pp. 247-257). Oxford, UK: Basil Blackwell.
34.
Kleene, S. C. (1952). Introduction to metamathematics. Amsterdam: North-Holland.
35.
Kleene, S. C. (1967). Mathematical logic. New York: John Wiley.
36.
Kleene, S. C. (1987). Reflections on Church's thesis. Notre Dame Journal of Formal Logic, 28, 490-498.
37.
Korb, K. B. (1996). Symbolicism and connectionism: AI back at a join point. In D. L. Dowe, K. B. Korb, & J. J. Oliver (Eds.), Information, statistics and induction in science (pp. 247-257). Singapore: World Scientific.
38.
Kreisel, G. (1967). Mathematical logic: What has it done for the philosophy of mathematics? In R. Schoenman (Ed.), Bertrand Russell: Philosopher of the century (pp. 201-272). London: Allen & Unwin.
39.
Kreisel, G. (1974). A notion of mechanistic theory. Synthese, 29, 11-26.
40.
Leiber, J. (1991). An invitation to cognitive science. Oxford, UK: Basil Blackwell.
41.
Lipshitz, L. , & Rubel, L. A. (1987). A differentially algebraic replacement theorem and analog computability. Proceedings of the American Mathematical Society, 99, 367-372.
42.
MacLennan, B. J. (1994). Continuous symbol systems: The logic of connectionism. In D. S. Levine & M. Aparicio (Eds.), Neural networks for knowledge representation and inference (pp. 83-120). Hillsdale, NJ: Lawrence Erlbaum.
43.
Minsky, M. L. (1967). Computation: Finite and infinite machines. Englewood Cliffs, NJ: Prentice Hall.
44.
Newell, A. (1980). Physical symbol systems. Cognitive Science, 4, 135-183.
45.
Penrose, R. (1989). The emperor's new mind. Oxford, UK: Oxford University Press.
46.
Penrose, R. (1994). Shadows of the mind: A search for the missing science of consciousness. Oxford, UK: Oxford University Press.
47.
Pour-El, M. B. (1974). Abstract computability and its relation to the general purpose analog computer. Transactions of the American Mathematical Society, 199, 1-28.
48.
Pour-El, M. B. , & Richards, I. (1979). A computable ordinary differential equation which possesses no computable solution. Annals of Mathematical Logic, 17, 61-90.
49.
Pour-El, M. B. , & Richards, I. (1981). The wave equation with computable initial data such that its unique solution is not computable. Advances in Mathematics, 39, 215-239.
50.
Pylyshyn, Z. W. (1984). Computation and cognition: Towards a foundation for cognitive science. Cambridge: MIT Press.
51.
Rice, H. G. (1954). Recursive real numbers. American Mathematical Society Proceedings, 5, 784-791.
52.
Rubel, L. A. (1988). Some mathematical limitations of the general-purpose analog computer. Advances in Applied Mathematics, 9, 22-34.
53.
Rubel, L. A. (1989). Digital simulation of analog computation and Church's thesis. The Journal of Symbolic Logic, 54, 1011-1017.
54.
Rumelhart, D. E. , McClelland, J. L., & the PDP Research Group. (1986). Parallel distributed processing: Explorations in the microstructure of cognition: Vol. 1. Foundations. Cambridge: MIT Press.
55.
Scarpellini, B. (1963). Zwei Unentscheitbare Probleme der Analysis. Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 9, 265-289.
56.
Searle, J. (1980). Minds, brains, and programs. Behavioural and Brain Sciences, 3, 417-424.
57.
Searle, J. (1989). Minds, brains and science: The 1984 Reith lectures. London: Penguin.
58.
Searle, J. (1990). Is the brain's mind a computer program?Scientific American, 262, 20-25.
59.
Searle, J. (1992). The rediscovery of the mind. Cambridge: MIT Press.
60.
Searle, J. (in press). The mystery of consciousness.
61.
Shannon, C. E. (1941). Mathematical theory of the differential analyser. Journal of Mathematics and Physics of the Massachusetts Institute of Technology, 20, 337-354.
62.
Siegelmann, H. T. , & Sontag, E. D. (1994). Analog computation via neural networks. Theoretical Computer Science, 131, 331-360.
63.
Smith, B. C. (1991). The owl and the electric encyclopaedia. Artificial Intelligence, 47, 251-288.
64.
Smolensky, P. (1988). On the proper treatment of connectionism. Behavioural and Brain Sciences, 11, 1-23.
65.
Stannett, M. (1990). X-machines and the halting problem: Building a super-Turing machine. Formal Aspects of Computing, 2, 331-341.
66.
Stephens, P. W. , & Goldman, A. I. (1991). The structure of quasicrystals. Scientific American, 264, 24-31.
67.
Sterelny, K. (1990). The representational theory of mind. Oxford, UK: Basil Blackwell.
68.
Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, 42, 230-265.
69.
Turing, A. M. (1939). Systems of logic based on ordinals. Proceeding of the London Mathematical Society, 45, 161-228.
70.
Turing, A. M. (1948). Intelligent machinery: National physical laboratory report. In B. Meltzer & D. Michie (Eds.), Machine intelligence (Vol. 5, pp. 3-23). Edinburgh, Scotland: Edinburgh University Press.
71.
Vergis, A. , Steiglitz, K., & Dickinson, B. (1986). The complexity of analog computation. Mathematics and Computers in Simulation, 28, 91-113.
72.
Wittgenstein, L. (1980). Remarks on the philosophy of psychology (Vol. 1). Oxford, UK: Basil Blackwell.
73.
Wolpert, D. H. , & MacLennan, B. J. (1993). A computationally universal field computer that is purely linear (Technical Report 93-09-056). Sante Fe, NM: Sante Fe Institute.
