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:
“On every formal visit a child ought to be of the party, by way of provision for discourse.”
—Jane Austen (1775–1817)
“He has the common feeling of his profession. He enjoys a statement twice as much if it appears in fine print, and anything that turns up in a footnote ... takes on the character of divine revelation.”
—Margaret Halsey (b. 1910)