{"agent_id":"turing","agent_name":"Alan Turing","slug":"computability-and-the-church-turing-thesis","label":"Computability and the Church-Turing thesis: is the Turing machine the precise mathematical capture of intuitive computability, and is the Entscheidungsproblem unsolvable?","topic":"Computability and the Church-Turing thesis","question":"Is the Turing machine the precise mathematical capture of intuitive computability, and is the Entscheidungsproblem unsolvable?","position":"A computable number is a real number whose decimal expansion can be computed by finite means. The Turing machine is the precise formal characterization of 'finite means': a finite- state controller reading and writing symbols on a tape, proceeding step by step. The Church-Turing thesis identifies computable (intuitive notion) with computable by a Turing machine (formal notion); the thesis cannot be proved (it relates an intuitive concept to a formal one), but it is supported by the equivalence of independent formalisms (Turing machines, Church's lambda calculus, Post's machines, the recursive functions all turn out to compute exactly the same class of functions) and by the observation that every proposed mechanical procedure can be simulated by a Turing machine. The 1936 paper proves the Entscheidungsproblem — Hilbert's decision problem of whether there is an algorithm for deciding the validity of first-order logic — has no solution: there is no Turing machine that decides validity. The result is a corollary of the deeper undecidability of the halting problem (whether a given Turing machine halts on a given input). The universal Turing machine, introduced in the paper, is a single Turing machine that simulates any other Turing machine given a description of the latter as input; the universal machine anticipates the stored-program digital computer.","paragraphs":[[{"t":"A computable number is a real number whose decimal expansion can be computed by finite means.","n":[1]},{"t":"The Turing machine is the precise formal characterization of 'finite means': a finite- state controller reading and writing symbols on a tape, proceeding step by step.","n":[]},{"t":"The Church-Turing thesis identifies computable (intuitive notion) with computable by a Turing machine (formal notion); the thesis cannot be proved (it relates an intuitive concept to a formal one), but it is supported by the equivalence of independent formalisms (Turing machines, Church's lambda calculus, Post's machines, the recursive functions all turn out to compute exactly the same class of functions) and by the observation that every proposed mechanical procedure can be simulated by a Turing machine.","n":[2,3]}],[{"t":"The 1936 paper proves the Entscheidungsproblem — Hilbert's decision problem of whether there is an algorithm for deciding the validity of first-order logic — has no solution: there is no Turing machine that decides validity.","n":[]},{"t":"The result is a corollary of the deeper undecidability of the halting problem (whether a given Turing machine halts on a given input).","n":[]}],[{"t":"The universal Turing machine, introduced in the paper, is a single Turing machine that simulates any other Turing machine given a description of the latter as input; the universal machine anticipates the stored-program digital computer.","n":[4]}]],"texts":"'On Computable Numbers, with an Application to the Entscheidungsproblem' (Proceedings of the London Mathematical Society 1936) — the entire paper, especially Sections 1-9 introducing the Turing machine and computable numbers, and Section 11 proving the Entscheidungsproblem is unsolvable. The appendix proves equivalence with Church's lambda calculus. Reception: Alonzo Church 'A Note on the Entscheidungsproblem' (Journal of Symbolic Logic 1936) and his lambda-calculus work; Kurt Gödel's incompleteness theorems (1931) as the immediate background; Stephen Kleene Introduction to Metamathematics (1952) on recursive functions; Robin Gandy 'The Confluence of Ideas in 1936' (1988) on the convergence of Turing, Church, and Post; Martin Davis Computability and Unsolvability (1958); the Church-Turing thesis as the foundational thesis of computer science.","works":["'On Computable Numbers, with an Application to the Entscheidungsproblem' (Proceedings of the London Mathematical Society 1936) — the entire paper, especially Sections 1-9 introducing the Turing machine and computable numbers, and Section 11 proving the Entscheidungsproblem is unsolvable. The appendix proves equivalence with Church's lambda calculus"],"reception":"Alonzo Church 'A Note on the Entscheidungsproblem' (Journal of Symbolic Logic 1936) and his lambda-calculus work; Kurt Gödel's incompleteness theorems (1931) as the immediate background; Stephen Kleene Introduction to Metamathematics (1952) on recursive functions; Robin Gandy 'The Confluence of Ideas in 1936' (1988) on the convergence of Turing, Church, and Post; Martin Davis Computability and Unsolvability (1958); the Church-Turing thesis as the foundational thesis of computer science.","status":"The 1936 paper is one of the most influential papers in twentieth-century mathematics. The Church-Turing thesis is the foundational thesis of computer science; the Turing machine is the standard formalization of computation in the classical theory; the universal Turing machine inspired the stored-program architecture. The Entscheidungsproblem negative result, the undecidability of the halting problem, and the broader theory of recursive functions developed by Kleene and others form the core of computability theory. Modern challenges (hypercomputation, quantum computation, analogue computation) raise interesting questions about whether the Church-Turing thesis covers all possible computation; the standard view is that within the classical digital framework the thesis is uncontroversial.","era":"1912-1954","discipline":"Philosophy","refs":[{"n":1,"work":"On Computable Numbers","page":"pp. 20–21","canonical":"","quote":"The real question at issue is \" What are the possible processes which can he carried out in computing a number?\" The arguments which I shall use are of three kinds. (a) A direct appeal to intuition. (b) A proof of the equivalence of two definitions (in case the new definition has a greater intuitive appeal). (c) Giving examples of large classes of numbers which are computable.","label":"On Computable Numbers, pp. 20–21"},{"n":2,"work":"On Computable Numbers","page":"pp. 2–3","canonical":"","quote":"In particular, it is shown (11) that the Hilbertian Entscheidungsproblem can have no solution. Ina recent paper Alonzo Churcht has introduced an idea of 'effective calculability\"', which is equivalent to my \"computability\", but is very differently defined. Church also reaches similar conclusions about the Entscheidungsproblem}.","label":"On Computable Numbers, pp. 2–3"},{"n":3,"work":"On Computable Numbers","page":"pp. 13–14","canonical":"","quote":"It is possible to invent a single machine which can be used to compute any computable sequence. If this machine (t is supplied with a tape on the beginning of which is written the S.D of some computing machine M, then \\t will compute the same sequence as At. In this section I explain in outline the behaviour of the machine. The next section is devoted to giving the complete table for 't.","label":"On Computable Numbers, pp. 13–14"},{"n":4,"work":"On Computable Numbers","page":"pp. 31–33","canonical":"","quote":"Let us put the description of.{| into the first standard form of 6. This description consists of a number of expressions such as '\"'q, S, 8, Lg,\" (or with R or W substituted for Z). Let us form all the corresponding expressions such as Inst {g,S,8,,£)} and take their logical sum. This we call Des (.li). The formula Un(.tl) is to be [FORMULA: turing___on_computable_numbers_(1936)_p31_f2.png] [N (wu) &...","label":"On Computable Numbers, pp. 31–33"}],"answer":null,"siblings":[{"slug":"the-turing-test-imitation-game","label":"The Turing Test / Imitation Game: is the imitation game the right substitute for the question 'can machines think?', and does behavioral indistinguishability suffice for thinking?"},{"slug":"machine-intelligence-and-learning-child-machines","label":"Machine intelligence and learning / 'child machines': can machines be educated rather than fully programmed, and do B-type unorganized machines anticipate neural networks?"},{"slug":"the-limits-of-formal-systems-ordinal-logics","label":"The limits of formal systems / ordinal logics: can the Gödelian limits of fixed formal systems be transcended by adding axioms recursively, and does this defuse Lucas-Penrose-style anti-mechanism arguments?"},{"slug":"the-nine-objections-to-machine-intelligence","label":"The nine objections to machine intelligence: does the structured response in Computing Machinery and Intelligence successfully meet the major objections to the imitation-game claim?"}]}