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, since a number of notions, including Turing computability, coincide in identifying this class of functions, and nobody has yet found something that is effective, intuitively, but not recursive.

Philosophy dictionary. . 2011.

Look at other dictionaries:

  • 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 (constructive mathematics) — In constructive mathematics, Church s thesis is the mathematical assertion that all total functions are recursive. It gets its name after the informal Church–Turing thesis, which states that every algorithm is in fact a recursive function, but… …   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

  • 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… …   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

  • CHURCH (A.) — CHURCH ALONZO (1903 ) Mathématicien et logicien, philosophe et historien de la logique, Alonzo Church est né à Washington. Professeur de mathématiques à l’université de Princeton, directeur du Journal of Symbolic Logic , il est selon Kneale «le… …   Encyclopédie Universelle

  • 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 News — Type Weekly newspaper Format Tabloid Owner Deseret News Publishing Company (Deseret Management Corporation) Editor …   Wikipedia

  • Church (surname) — Church is an English surname. Notable people with the surname include: Albert T. Church (born 1947), Vice Admiral in the United States Navy Alonzo Church (1903–1995), logician, famous for the Church Turing thesis and lambda calculus Captain… …   Wikipedia

Share the article and excerpts

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