In the computational literature the term
“Church-Turing thesis” is applied to a
variety of different propositions usually not equivalent to the original thesis—CTT-O; some even go far beyond
anything either Church or Turing wrote.
Several but not all are fundamental assumptions of computer science. Others
(such as the various physical computability theses we have discussed) are important in the philosophy of computing
and the philosophy of physics but are
highly contentious; indeed, the label
“Church-Turing thesis” should not mislead computer scientists or anyone else
into thinking they are established fact
or even that Church or Turing endorsed
1. Aharonov, D. and Vazirani, U. V. Is quantum mechanics
falsifiable? A computational perspective on the
foundations of quantum mechanics. Chapter in
Computability: Gödel, Turing, Church and Beyond, B. J.
Copeland, C.J. Posy, and O. Shagrir, Eds. MI T Press,
Cambridge, MA, 2013.
2. Andréka, H., Németi, I., and Németi, P. General relativistic
hypercomputing and foundation of mathematics. Natural
Computing 8, 3 (Sept. 2009), 499–516.
3. Bernstein, E. and Vazirani, U. Quantum complexity
theory. SIAM Journal on Computing 26, 5 (Oct. 1997),
4. Castelvecchi, D. Paradox at the heart of mathematics
makes physics problem unanswerable. Nature 528
(Dec. 9, 2015), 207.
5. Church, A. An unsolvable problem of elementary
number theory. American Journal of Mathematics 58,
2 (Apr. 1936), 345–363.
6. Copeland, B.J. The broad conception of computation.
American Behavioral Scientist 40, 6 (May 1997),
7. Copeland, B.J. Even Turing machines can compute
uncomputable functions. Chapter in Unconventional
Models of Computation, C. Calude, J. Casti, and M.
Dinneen, Eds. Springer, Singapore, 1998.
8. Copeland, B.J. Narrow versus wide mechanism:
Including a re-examination of Turing’s views on the
mind-machine issue. The Journal of Philosophy 97, 1
(Jan. 2000), 5–32.
9. Copeland, B.J. Hypercomputation. Minds and Machines
12, 4 (Nov. 2002), 461–502.
10. Copeland, B.J. The Essential Turing: Seminal Writings
in Computing, Logic, Philosophy, Artificial Intelligence,
and Artificial Life, Plus the Secrets of Enigma. Oxford
University Press, Oxford, U.K., 2004.
11. Copeland, B.J. and Proudfoot, D. Alan Turing’s
forgotten ideas in computer science. Scientific
American 280, 4 (Apr. 1999), 98–103.
12. Copeland, B.J. and Shagrir, O. Do accelerating Turing
machines compute the uncomputable? Minds and
Machines 21, 2 (May 2011), 221–239.
13. Copeland, B.J. and Shagrir, O. Turing versus Gödel on
computability and the mind. Chapter in Computability:
Gödel, Turing, Church, and Beyond, B. J. Copeland,
C. J. Posy, and O. Shagrir, Eds. MI T Press, Cambridge,
14. Cubitt, T. S., Perez-Garcia, D., and Wolf, M. M.
Undecidability of the spectral gap. Nature 528, 7581
(Dec. 2015), 207–211.
15. Davis, M. Why Gödel didn’t have Church’s thesis.
Information and Control 54, 1-2 (July 1982), 3–24.
16. Dershowitz, N. and Gurevich, Y. A natural
axiomatization of computability and proof of Church’s
thesis. Bulletin of Symbolic Logic 14, 3 (Sept. 2008),
17. Deutsch, D. Quantum theory, the Church- Turing
principle and the universal quantum computer.
Proceedings of the Royal Society of London A:
Mathematical, Physical and Engineering Sciences 400,
1818 (July 1985), 97–117.
18. Doyle, J. What is Church’s thesis? An outline. Minds
and Machines 12, 4 (Nov. 2002), 519–520.
19. Eisert, J., Müller, M.P., and Gogolin, C. Quantum
measurement occurrence is undecidable. Physical
Review Letters 108, 26 (June 2012), 1–5.
20. Gandy, R.O. Church’s thesis and principles for
mechanisms. In Proceedings of the Kleene
Symposium, J. Bar wise, H. J. Keisler, and K. Kunen,
Eds. (Madison, WI, June 1978). North-Holland,
Amsterdam, Netherlands, 1980.
21. Goldreich, O. Computational Complexity: A Conceptual
Perspective. Cambridge University Press, New York, 2008.
22. Gurevich, Y. What is an algorithm? In Proceedings of
the 38th Conference on Current Trends in the Theory
and Practice of Computer Science (Špindle rv Mlýn,
Czech Republic, Jan. 21–27), M. Bieliková, G. Friedrich,
G. Gottlob, S. Katzenbeisser, and G. Turán, Eds.
Springer, Berlin, Heidelberg, Germany, 2012.
23. Harel, D. Algorithmics: The Spirit of Computing,
Second Edition. Addison-Wesley, Reading, MA, 1992.
24. Hopcroft, J.E. and Ullman, J.D. Introduction to
Automata Theory, Languages, and Computation.
Addison-Wesley, Reading, MA, 1979.
25. Kleene, S.C. Introduction to Metamathematics. Van
Nostrand, New York, 1952.
26. Komar, A. Undecidability of macroscopically
distinguishable states in quantum field theory.
Physical Review 133, 2B (Jan. 1964), 542–544.
27. Kreisel, G. Mathematical logic: What has it done for
the philosophy of mathematics? Chapter in Bertrand
Russell: Philosopher of the Century, R. Schoenman, Ed.
Allen and Unwin, London, U.K., 1967.
28. Kripke, S.A. Another approach: The Church-Turing
‘thesis’ as a special corollary of Gödel’s completeness
theorem. Chapter in Computability: Gödel, Turing,
Church, and Beyond, B.J. Copeland, C. J. Posy, and O.
Shagrir, Eds. MI T Press, Cambridge, MA, 2013.
29. Lewis, H. R. and Papadimitriou, C.H. Elements of the
Theory of Computation. Prentice Hall, Upper Saddle
River, NJ, 1981.
30. Moschovakis, Y.N. and Paschalis, V. Elementary
algorithms and their implementations. Chapter in New
Computational Paradigms: Changing Conceptions of
What Is Computable, S.B. Cooper, B. Lowe, and A.
Sorbi, Eds. Springer, New York, 2008.
31. Piccinini, G. The physical Church-Turing thesis: Modest
or bold? The British Journal for the Philosophy of
Science 62, 4 (Aug. 2011), 733–769.
32. Pitowsky, I. The physical Church thesis and physical
computational complexity. Iyyun 39, 1 (Jan. 1990), 81–99.
33. Post, E.L. Finite combinatory processes: Formulation
I. The Journal of Symbolic Logic 1, 3 (Sept. 1936),
34. Pour-El, M.B. and Richards, I.J. The wave equation
with computable initial data such that its unique
solution is not computable. Advances in Mathematics
39, 3 (Mar. 1981), 215–239.
35. Sieg, W. Mechanical procedures and mathematical
experience. Chapter in Mathematics and Mind, A.
George, Ed. Oxford University Press, New York, 1994.
36. Turing, A.M. On computable numbers, with an
application to the Entscheidungsproblem (1936); in
37. Turing, A.M. Lecture on the Automatic Computing
Engine (1947); in Copeland. 10
38. Turing, A.M. Intelligent Machinery (1948); in
39. Wolfram, S. Undecidability and intractability in
theoretical physics. Physical Review Letters 54, 8 (Feb.
40. Yao, A.C.C. Classical physics and the Church-Turing
thesis. Journal of the ACM 50, 1 (Jan. 2003), 100–105.
B. Jack Copeland ( email@example.com) is
Distinguished Professor of Philosophy at the University of
Canterbury in Christchurch, New Zealand, and Director of
the Turing Archive for the History of Computing, also at
the University of Canterbury.
Oron Shagrir ( firstname.lastname@example.org) is Schulman
Professor of Philosophy and Cognitive Science at the
Hebrew University of Jerusalem, Jerusalem, Israel.
Copyright held by the authors.
Publication rights licensed to ACM. $15.00
classical concept, saying, “[E]quilibrat-
ing can be so easily, reproducibly, and
mindlessly accomplished” that we may
“take the operation of equilibrating as
an effective one,” even if “the functions
computable in principle given Turing’s
operations and equilibrating include
Over the years, there have been sever-
al departures from Turing’s 1936 analy-
sis, as the needs of computer science
led to a broadening of the algorithm
concept. For example, Turing’s fourth
axiom, which bounds the number of
parts of a system that can be changed
simultaneously, became irrelevant
when the algorithm concept broadened
to cover parallel computations. The fu-
ture computational landscape might
conceivably include more extensive re-
visions of the concept, if, for example,
physicists were to discover that hard-
ware effective in Doyle’s extended sense
is a realistic possibility.
If such hardware were to be developed—hardware in which operations
are effective in the sense of being “
easily, reproducibly, and mindlessly accomplished” but not bounded by Turing
computability—then would the appropriate response by computer scientists
be to free the algorithm concept from
CTT-A? Or should CTT-A remain as a
constraint on algorithms, with instead
two different species of computation being recognized, called, say, algorithmic
computation and non-algorithmic computation? Not much rides on a word, but
we note we prefer “effective computation” for computation that is bounded
by Turing computability and “
neo-effective computation” for computation
that is effective in Doyle’s sense and not
bounded by Turing computability, with
“neo” indicating a new concept related
to an older one.
The numerous examples of notional
“hypercomputers” (see Copeland9 for
a review) prompt similar questions. Interestingly, a study of the expanding literature about the concept of an infinite-time Turing machine, introduced by
Joel Hamkins and Andy Lewis in 2000,
shows that a number of computer scientists are prepared to describe the in-finite-time machine as computing the
halting function. Perhaps this indicates
the concept of computation is already
in the process of bifurcating into “
effective” and “neo-effective” computation.