Church–Turing thesis

E26972

foundational principle in theoretical computer science philosophical thesis about computation thesis in computability theory

The Church–Turing thesis is a foundational principle in computability theory stating that any function that can be effectively computed by an algorithm can be computed by a Turing machine (or equivalently by other formal models of computation).

Jump to: Surface forms Statements Referenced by

Observed surface forms (4)

Surface form	Occurrences
Church–Turing–Deutsch principle	1
extended Church–Turing thesis	1
physical Church–Turing thesis	1
strong Church–Turing thesis	1

Statements (53)

Predicate	Object
instanceOf	foundational principle in theoretical computer science ⓘ philosophical thesis about computation ⓘ thesis in computability theory ⓘ
associatedWith	Alan Turing ⓘ Alonzo Church ⓘ Stephen Kleene ⓘ
coreClaim	all reasonable models of computation have the same class of computable functions ⓘ equivalence of informal notion of effective calculability and formal models of computation ⓘ no algorithm can compute more functions than a Turing machine can ⓘ
field	computability theory ⓘ mathematical logic ⓘ philosophy of computation ⓘ theoretical computer science ⓘ
hasVariant	Church–Turing thesis self-linksurface differs ⓘ surface form: Church–Turing–Deutsch principle Church–Turing thesis self-linksurface differs ⓘ surface form: extended Church–Turing thesis Church–Turing thesis self-linksurface differs ⓘ surface form: physical Church–Turing thesis Church–Turing thesis self-linksurface differs ⓘ surface form: strong Church–Turing thesis
historicalContext	arose from attempts to formalize the notion of effective calculability ⓘ formulated in the 1930s ⓘ
implies	any algorithmic computation can be simulated by a Turing machine ⓘ no stronger notion of algorithmic computability than Turing computability exists ⓘ
influences	cognitive science ⓘ complexity theory ⓘ design of programming languages ⓘ foundations of mathematics ⓘ philosophy of mind ⓘ
involves	formalization of computation ⓘ informal notion of effective procedure ⓘ
namedAfter	Alan Turing ⓘ Alonzo Church ⓘ
not	mathematically provable statement within standard formal systems ⓘ
relatedTo	Gödel's incompleteness theorems ⓘ surface form: Gödel’s incompleteness theorems Entscheidungsproblem ⓘ surface form: Hilbert’s Entscheidungsproblem computationalism in philosophy of mind ⓘ recursive function theory ⓘ
relatesToConcept	Halting problem ⓘ Turing machine ⓘ algorithm ⓘ algorithmic process ⓘ computable function ⓘ computational model equivalence ⓘ decidability ⓘ effective calculability ⓘ general recursive function ⓘ mechanical procedure ⓘ partial recursive function ⓘ undecidability ⓘ λ‑calculus ⓘ
statedAs	any effectively computable function can be computed by a general recursive function ⓘ any effectively computable function can be computed by a λ‑definable function ⓘ every effectively calculable function is computable by a Turing machine ⓘ
status	methodological principle in computability theory ⓘ unprovable but widely accepted thesis ⓘ

Referenced by (10)

Full triples — surface form annotated when it differs from this entity's canonical label.

Church–Turing thesis → hasVariant → Church–Turing thesis self-linksurface differs ⓘ

this entity surface form: physical Church–Turing thesis

Church–Turing thesis → hasVariant → Church–Turing thesis self-linksurface differs ⓘ

this entity surface form: strong Church–Turing thesis

Church–Turing thesis → hasVariant → Church–Turing thesis self-linksurface differs ⓘ

this entity surface form: extended Church–Turing thesis

Church–Turing thesis → hasVariant → Church–Turing thesis self-linksurface differs ⓘ

this entity surface form: Church–Turing–Deutsch principle

Church (surname) → knownFor → Church–Turing thesis ⓘ

subject surface form: Alonzo Church

Alonzo Church → notableWork → Church–Turing thesis ⓘ

Computing Machinery and Intelligence → relatedTo → Church–Turing thesis ⓘ

Entscheidungsproblem → relatedTo → Church–Turing thesis ⓘ

Gödel's incompleteness theorems → relatedTo → Church–Turing thesis ⓘ

On Computable Numbers with an Application to the Entscheidungsproblem → relatedTo → Church–Turing thesis ⓘ

subject surface form: On Computable Numbers, with an Application to the Entscheidungsproblem