Church–Turing thesis  

From The Art and Popular Culture Encyclopedia

(Redirected from Church's thesis)
Jump to: navigation, search

Related e

Wikipedia
Wiktionary
Shop


Featured:

In computability theory, the Church–Turing thesis (also known as the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a hypothesis about the nature of computable functions. It states that a function on the natural numbers is computable by a human being following an algorithm, ignoring resource limitations, if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and the British mathematician Alan Turing. Before the precise definition of computable function, mathematicians often used the informal term effectively calculable to describe functions that are computable by paper-and-pencil methods.

See also




Unless indicated otherwise, the text in this article is either based on Wikipedia article "Church–Turing thesis" or another language Wikipedia page thereof used under the terms of the GNU Free Documentation License; or on research by Jahsonic and friends. See Art and Popular Culture's copyright notice.

Personal tools