Church's thesis

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

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

  • 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 encoding — In mathematics, Church encoding is a means of embedding data and operators into the lambda calculus, the most familiar form being the Church numerals, a representation of the natural numbers using lambda notation. The method is named for Alonzo… …   Wikipedia

  • Church–Turing–Deutsch principle — In computer science and quantum physics, the Church–Turing–Deutsch principle (CTD principle) is a stronger, physical form of the Church–Turing thesis formulated by David Deutsch in 1985. The principle states that a universal computing device can… …   Wikipedia

Share the article and excerpts

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