- Theorem due to the American mathematician and philosopher Alonzo Church (1903– ) stating that the theorems of the predicate calculus do not form a general recursive set. Given Church's thesis, this means that there is no decision procedure or algorithm for deciding whether an arbitrary formula of the first-order predicate calculus is a theorem of the calculus.
Philosophy dictionary. Academic. 2011.
Look at other dictionaries:
Church–Rosser theorem — The Church–Rosser theorem states that if there are two distinct reductions starting from the same lambda calculus term, then there exists a term that is reachable from each reduct via a (possibly empty) sequence of reductions. This is symbolized… … Wikipedia
Church-Rosser-Theorem — Dieser Artikel wurde auf der Qualitätssicherungsseite des Portals Mathematik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Mathematik auf ein akzeptables Niveau zu bringen. Dabei werden Artikel gelöscht, die nicht… … Deutsch Wikipedia
Church–Turing thesis — Church s thesis redirects here. For the constructive mathematics assertion, see Church s thesis (constructive mathematics). In computability theory, the Church–Turing thesis (also known as the Church–Turing conjecture, Church s thesis, Church s… … Wikipedia
Theorem — The Pythagorean theorem has at least 370 known proofs In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements … Wikipedia
Church's thesis — ▪ mathematics also called Church s Theorem, a principle formulated by the 20th century American logician Alonzo Church, stating that the recursive functions are the only functions that can be mechanically calculated. The theorem implies… … Universalium
Church, Alonzo — born June 14, 1903, Washington, D.C., U.S. died Aug. 11, 1995, Hudson, Ohio U.S. mathematician. He earned a Ph.D. from Princeton University. His contributions to number theory and the theories of algorithms and computability laid the foundations… … Universalium
Church's thesis — The thesis that every effectively computable function is general recursive. A thesis rather than a theorem, because the notion of effective computability remains intuitive rather than mathematically defined. The thesis is generally believed,… … Philosophy dictionary
History of the Church-Turing thesis — This article is an extension of the history of the Church Turing thesis.The debate and discovery of the meaning of computation and recursion has been long and contentious. This article provides detail of that debate and discovery from Peano s… … Wikipedia
History of the Church–Turing thesis — This article is an extension of the history of the Church–Turing thesis. The debate and discovery of the meaning of computation and recursion has been long and contentious. This article provides detail of that debate and discovery from Peano s… … Wikipedia
Alonzo Church — This article is about the mathematician and logician. For the president of the University of Georgia, see Alonzo S. Church. Alonzo Church Alonzo Church (1903–1995) … Wikipedia