Church's theorem
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. . 2011.

Look at other dictionaries:

  • 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–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'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'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

  • Trakhtenbrot's theorem — In logic (usually computational) and finite model theory, Trakhtenbrot s theorem (due to Boris Trakhtenbrot) states that the problem of validity in the class of all finite models is undecidable. In fact, the class of valid sentences over finite… …   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[1] 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, 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

  • 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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”