In 'On Computable Numbers, with an Application to the Entscheidungsproblem' (1936), Turing states that no attempt has yet been made to show that his machine-defined computable numbers include all numbers which would 'naturally be regarded as computable', that all arguments for this identification are 'fundamentally, appeals to intuition', and that the real question at issue is 'What are the possible processes which can be carried out in computing a number?'. Two neighboring strands of the source record lie outside this question: the promise (in the paper's abstract) of a theory of computable functions of a real variable was discharged by the later field of computable analysis, and Turing's hedged aside on the non-computable sequence delta -- that any assigned number of figures may be calculable 'but not by a uniform process' -- is an informal observation later absorbed into the theories of oracles and non-uniform computation, not a well-posed open problem. The open core, pursued intensively since 1936, is whether the identification of intuitive computability with Turing-machine computability can be rigorously grounded or refuted. No intuitively acceptable effective procedure exceeding Turing computability has been found; rigorous derivations from precise axioms about computation exist (Gandy's principles for mechanisms, Dershowitz and Gurevich's axiomatization, Kripke's completeness-theoretic derivation, Sieg's axiomatic analyses) but are contested as relocating rather than discharging the intuition; and the physically generalized version remains genuinely open as a descendant question.

Background

Turing's 1936 paper 'On Computable Numbers, with an Application to the Entscheidungsproblem' (Proceedings of the London Mathematical Society, series 2, volume 42, pages 230-265) introduced the computing machines now called Turing machines. In Turing's original setup an automatic machine (a-machine) is a device with finitely many internal configurations ('m-configurations', the precursors of machine states), a one-dimensional tape divided into squares each carrying one symbol, and fully determined motion: at every moment the machine's next action depends only on its current m-configuration and the symbol on the scanned square. A machine that never prints more than finitely many figures (0s and 1s) is called circular; otherwise it is circle-free. A sequence is computable if some circle-free machine prints it, and a real number is computable if it differs by an integer from the number computed by a circle-free machine. Each machine has a description number (D.N.), an integer encoding its transition table; a number is satisfactory if it is the D.N. of a circle-free machine. In section 8 Turing proves, by a corrected form of Cantor's diagonal argument, that no machine can decide which numbers are satisfactory, and he uses this to show that the Entscheidungsproblem -- Hilbert's demand for a general method deciding derivability (equivalently, validity) in first-order logic -- has no solution. The whole argument, however, rests on a step Turing flags himself: the identification of 'computable' in his formal sense with intuitively calculable. Church (1936) had simultaneously identified effective calculability with lambda-definability (definability of functions in Church's lambda calculus, a formal system for functions built from variable binding and application), and Turing proved the two formal notions equivalent. In section 9, 'The extent of the computable numbers', Turing concedes that no attempt has yet been made to show the computable numbers include all numbers which would naturally be regarded as computable, that all arguments which can be given are 'fundamentally, appeals to intuition, and for this reason rather unsatisfactory mathematically', and that the real question at issue is 'What are the possible processes which can be carried out in computing a number?'. He then gives three arguments: a direct analysis of a human computer's limitations (finitely many states of mind, finitely many squares observed at once, at most one symbol altered per elementary step), an equivalence proof with definability in the formalism of the Hilbert functional calculus (Hilbert's name for first-order predicate logic, his 'restricted functional calculus'; section 9, argument II), and large classes of examples (algebraic numbers, pi, e, zeros of Bessel functions; section 10). Two neighboring remarks are sometimes conflated with this question but lie outside it. First, inside argument II of section 9, Turing defines the sequence delta (written with the Greek letter) whose n-th figure is 1 or 0 according as n is or is not satisfactory; delta is not computable, by section 8, yet Turing adds, explicitly hedged ('so far as we know at present'), that any assigned number of figures of delta may be calculable 'but not by a uniform process', so that 'when sufficiently many figures of delta have been calculated, an essentially new method is necessary in order to obtain more figures'. Second, the paper's introductory abstract promises a sequel: 'I hope shortly to give an account of the relations of the computable numbers, functions, and so forth to one another. This will include a development of the theory of functions of a real variable expressed in terms of computable numbers.' Later vocabulary for the ideas surrounding the main question: Turing's 1939 'Systems of Logic Based on Ordinals' defines o-machines -- machines equipped with an oracle, a black-box 'unspecified means of solving number-theoretic problems' that is explicitly not a machine -- founding the theory of relative computability; and non-uniform computation (a different algorithm or advice string for each input length, as in Boolean circuit complexity; Karp and Lipton 1980) is the modern form of 'calculable, but not by a uniform process'. The identification of intuitive computability with Turing-machine computability is now called Turing's thesis or, with Church's variant, the Church-Turing thesis; its physical generalization asks whether any finite physical process can compute a sequence no Turing machine computes.

Problem Statement

Turing's 1936 question, restated source-faithfully: are all infinite binary sequences (equivalently, all real numbers) that would 'naturally be regarded as computable' -- that is, calculable by finite means, by whatever processes can actually be carried out in computing a number -- computable by Turing's automatic machines, and can this identification be established by something better than an appeal to intuition? The question is whether this identification can be grounded from precise principles or refuted by an intuitively acceptable counterexample, rather than resting on appeals to intuition. (1) Refutation: exhibit a precisely specified procedure that is intuitively acceptable as an effective calculation by finite means, yet computes a sequence that no Turing machine computes. For this branch an effective method is understood in the standard sense recorded in the Stanford Encyclopedia of Philosophy entry 'The Church-Turing Thesis': a method given by finitely many exact instructions in finitely many symbols, which produces the desired result in finitely many steps, can be carried out by a human being unaided except for paper and pencil, and demands no insight, intuition, or ingenuity. The converse inclusion (every machine-computable sequence is naturally computable) is uncontested. A physical reading of 'processes which can be carried out' (any finite physical process) belongs to the modern maximality thesis rather than to the identification Turing flagged in section 9; a physical refutation would address that descendant question and would not close this one. (2) Grounding: formulate precise axioms or principles about computation -- about human computers, classical algorithms, or discrete deterministic mechanisms -- and prove mathematically that every procedure satisfying them is Turing-machine computable. A grounding of this form closes the question only if the axioms or principles are supported as capturing the informal notion of effective calculability itself, rather than merely relocating the intuition into them; whether a given axiom system meets that standard is the standing locus at which derivations of this form are contested. In Turing's own framing, the underlying question is 'What are the possible processes which can be carried out in computing a number?' -- to be answered by exactly delimiting those processes.

References

  1. A. M. Turing (1936), 'On Computable Numbers, with an Application to the Entscheidungsproblem', Proceedings of the London Mathematical Society, series 2, 42: 230-265, DOI 10.1112/plms/s2-42.1.230, https://doi.org/10.1112/plms/s2-42.1.230
  2. A. M. Turing (1938), 'On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction', Proceedings of the London Mathematical Society, series 2, 43: 544-546, DOI 10.1112/plms/s2-43.6.544, https://doi.org/10.1112/plms/s2-43.6.544
  3. A. M. Turing (1937), 'Computability and λ-definability', The Journal of Symbolic Logic 2(4): 153-163, DOI 10.2307/2268280, https://doi.org/10.2307/2268280
  4. A. M. Turing (1939), 'Systems of Logic Based on Ordinals', Proceedings of the London Mathematical Society, series 2, 45: 161-228, DOI 10.1112/plms/s2-45.1.161, https://doi.org/10.1112/plms/s2-45.1.161
  5. Alonzo Church (1936), 'An Unsolvable Problem of Elementary Number Theory', American Journal of Mathematics 58: 345-363, DOI 10.2307/2371045, https://doi.org/10.2307/2371045
  6. Robin Gandy (1980), 'Church's Thesis and Principles for Mechanisms', in J. Barwise, H. J. Keisler, K. Kunen (eds.), The Kleene Symposium, North-Holland, 123-148, DOI 10.1016/S0049-237X(08)71257-6, https://doi.org/10.1016/S0049-237X(08)71257-6
  7. Nachum Dershowitz and Yuri Gurevich (2008), 'A Natural Axiomatization of Computability and Proof of Church's Thesis', Bulletin of Symbolic Logic 14(3): 299-350, DOI 10.2178/bsl/1231081370, https://doi.org/10.2178/bsl/1231081370
  8. Saul A. Kripke (2013), 'The Church-Turing "Thesis" as a Special Corollary of Gödel's Completeness Theorem', in B. J. Copeland, C. J. Posy, O. Shagrir (eds.), Computability: Turing, Gödel, Church, and Beyond, MIT Press, 77-104, DOI 10.7551/mitpress/8009.003.0005, https://doi.org/10.7551/mitpress/8009.003.0005
  9. Wilfried Sieg (2008), 'Church Without Dogma: Axioms for Computability', in S. B. Cooper, B. Löwe, A. Sorbi (eds.), New Computational Paradigms, Springer, 139-152, DOI 10.1007/978-0-387-68546-5_7, https://doi.org/10.1007/978-0-387-68546-5_7
  10. Andrzej Grzegorczyk (1955), 'Computable functionals', Fundamenta Mathematicae 42: 168-202, DOI 10.4064/fm-42-1-168-202, https://doi.org/10.4064/fm-42-1-168-202
  11. Marian Boykan Pour-El and J. Ian Richards (1989), Computability in Analysis and Physics, Springer, Perspectives in Mathematical Logic series, DOI 10.1007/978-3-662-21717-7, https://doi.org/10.1007/978-3-662-21717-7
  12. Klaus Weihrauch (2000), Computable Analysis: An Introduction, Springer, Berlin/Heidelberg, ISBN 978-3-540-66817-6 (hardcover), DOI 10.1007/978-3-642-56999-9, https://doi.org/10.1007/978-3-642-56999-9
  13. Richard M. Karp and Richard J. Lipton (1980), 'Some connections between nonuniform and uniform complexity classes', in Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing (STOC '80), 302-309, DOI 10.1145/800141.804678, https://doi.org/10.1145/800141.804678
  14. B. Jack Copeland, 'The Church-Turing Thesis', Stanford Encyclopedia of Philosophy, first published 8 January 1997, substantive revision 18 December 2023, https://plato.stanford.edu/entries/church-turing/
  15. Liesbeth De Mol, 'Turing Machines', Stanford Encyclopedia of Philosophy, substantive revision 21 May 2025, https://plato.stanford.edu/entries/turing-machine/
  16. Carlo Cellucci (2026), 'Turing's Unresolved Tension', Foundations of Science, DOI 10.1007/s10699-026-10047-2, https://doi.org/10.1007/s10699-026-10047-2
  17. Alan Turing (2004), 'On Computable Numbers, with an Application to the Entscheidungsproblem (1936)', in B. J. Copeland (ed.), The Essential Turing, Oxford University Press, 58-90, DOI 10.1093/oso/9780198250791.003.0005, https://doi.org/10.1093/oso/9780198250791.003.0005