Church's Thesis (constructive Mathematics)
In constructive mathematics, Church's thesis (CT) is an axiom which states that all total functions are computable. The axiom takes its name from the Church–Turing thesis, which states that every effectively calculable function is computable function, but the constructivist version is much stronger, claiming that every function is computable.
The axiom CT is incompatible with classical logic in sufficiently strong systems. For example, Heyting arithmetic (HA) with CT as an addition axiom is able to disprove some instances of the law of the excluded middle. However, Heyting arithmetic is equiconsistent with Peano arithmetic (PA) as well as with Heyting arithmetic plus Church's thesis. That is, adding either the law of the excluded middle or Church's thesis does not make Heyting arithmetic inconsistent, but adding both does.
Read more about Church's Thesis (constructive Mathematics): Formal Statement, Relationship To Classical Logic, Extended Church's Thesis
Famous quotes containing the words church and/or thesis:
“Among twelve apostles there must always be one who is as hard as stone, so that the new church may be built upon him.”
—Friedrich Nietzsche (1844–1900)
“Some have said that the thesis [of indeterminacy] is a consequence of my behaviorism. Some have said that it is a reductio ad absurdum of my behaviorism. I disagree with this second point, but I agree with the first. I hold further that the behaviorism approach is mandatory. In psychology one may or may not be a behaviorist, but in linguistics one has no choice.”
—Willard Van Orman Quine (b. 1908)