Formal Statement
In first-order theories such as HA, which cannot quantify over functions directly, CT is stated as an axiom schema which says that any definable function is computable, using Kleene's T predicate to define computability. For each formula φ(x,y) of two variables, the schema includes the axiom
This axiom asserts that, if for every x there is a y satisfying φ then there is in fact an e which is the Gödel number of a general recursive function that will, for every x, produce such a y satisfying the formula.
In higher-order systems that can quantify over functions directly, CT can be stated as a single axiom which says that every function from the natural numbers to the natural numbers is computable.
Read more about this topic: Church's Thesis (constructive Mathematics)
Famous quotes containing the words formal and/or statement:
“The spiritual kinship between Lincoln and Whitman was founded upon their Americanism, their essential Westernism. Whitman had grown up without much formal education; Lincoln had scarcely any education. One had become the notable poet of the day; one the orator of the Gettsyburg Address. It was inevitable that Whitman as a poet should turn with a feeling of kinship to Lincoln, and even without any association or contact feel that Lincoln was his.”
—Edgar Lee Masters (1869–1950)
“Truth is that concordance of an abstract statement with the ideal limit towards which endless investigation would tend to bring scientific belief, which concordance the abstract statement may possess by virtue of the confession of its inaccuracy and one-sidedness, and this confession is an essential ingredient of truth.”
—Charles Sanders Peirce (1839–1914)