Computability Theory

The Computability Concept 11

Church’s thesis, which relates an informal idea to a formal idea, is not itself a

mathematical statement capable of being given a proof. But one can look for evidence

for or against Church’s thesis; it all turns out to be evidence in favor.

One piece of evidence is the absence of counterexamples. That is, any function

examined thus far that mathematicians have felt was effectively calculable, has been

found to be computable.

Stronger evidence stems from the various attempts that different people made inde-

pendently, trying to formalize the idea of effective calculability. Alonzo Church used

λ-calculus; Alan Turing used