Proving Church's thesis

DOI10.1093/PHILMAT/8.3.244MaRDI QIDQ2701936zbMATH OpenOpenAlexFDO

Authors Robert Black

Publication date 9 January 2002

Published in Philosophia Mathematica. Series III (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/philmat/8.3.244

zbMATH Keywords

Church's thesiseffectively computable functionrecursive function

Mathematics Subject Classification ID

Philosophical and critical aspects of logic and foundations (03A05) Turing machines and related notions (03D10) Recursive functions and relations, subrecursive hierarchies (03D20)

Review text

The author argues against the traditional view that a proof of Church's Thesis (CT) is impossible. He repeats and supports the argument that CT has been proved in one direction (namely, that every recursive function is effectively computable), and he agrees (for example, with Shoenfield) that a proof in the other direction is conceivable (for example, by using suitable axioms for the notion of effectively computable function). He rejects recent arguments for the unprovability of CT by \textit{J. Folina} [ibid. 6, 302-323 (1998; Zbl 0916.03007)]. Her restriction to proofs in ZFC or some other standard axiom system stacks the deck against the provability of CT. The author points out that the notion of effectively computable function is not vague and can legitimately occur in mathematical proofs, although it does not occur in the standard axiom systems. This paper also contains an outline of an argument in favor of CT given by Saul Kripke (at a Logic Colloquium in Berlin in 1998), which seems to depend on the assumption that a function which can be shown to be computable within a first-order language must be recursive. Precise details of this argument are not given.

Recommendations

• On the impossibility of proving the ``hard-half of Church's thesis
• The status of Church's thesis
• On the Church-Turing thesis and relative recursion
• Squeezing arguments
• scientific article; zbMATH DE number 3930985
• From Logic to Physics: How the Meaning of Computation Changed over Time
• Human-effective computability
• A Natural Axiomatization of Computability and Proof of Church's Thesis
• Kalmár's argument against the plausibility of Church's thesis
• Constructive mathematics, Church's thesis, and free choice sequences

Cited in

(16)

• Church's thesis from the point of view of provability interpretation
• Kripke's paradox and the Church-Turing thesis
• The physical Church thesis as an explanation of the Galileo thesis
• Proving Church’s Thesis
• A Natural Axiomatization of Computability and Proof of Church's Thesis
• scientific article; zbMATH DE number 3930985 (Why is no real title available?)
• Human-effective computability
• Proving Things About the Informal
• Squeezing arguments
• What is the Church-Turing Thesis?
• Kalmár's argument against the plausibility of Church's thesis
• On the Church-Turing thesis and relative recursion
• Church's thesis and the variety of mathematical justifications
• On the impossibility of proving the ``hard-half of Church's thesis
• Computability, proof, and open-texture
• The decision problem for effective procedures

This page was built for publication: Proving Church's thesis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2701936)