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).

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

AI illustration

All labels observed (6)

Label	Occurrences
Church–Turing thesis canonical	20
extended Church–Turing thesis	2
physical Church–Turing thesis	2
Church–Turing–Deutsch principle	1
Church’s thesis	1
strong Church–Turing thesis	1

How this entity was disambiguated

This entity first appeared as the object of triple T211710 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: Church–Turing thesis
Context triple: [Alonzo Church, knownFor, Church–Turing thesis]

A. Turing machine
A Turing machine is an abstract computational model that manipulates symbols on an infinite tape according to a set of rules, providing a formal foundation for the concept of algorithm and computability.
B. On Computable Numbers with an Application to the Entscheidungsproblem
"On Computable Numbers, with an Application to the Entscheidungsproblem" is Alan Turing’s landmark 1936 paper that introduced the Turing machine model and founded the formal study of computability and the limits of algorithmic decision procedures.
C. von Neumann architecture
The von Neumann architecture is a foundational computer design model in which a single memory stores both program instructions and data, executed sequentially by a central processing unit.
D. Alan Turing
Alan Turing was a pioneering British mathematician and logician whose foundational work in computing and codebreaking established him as one of the principal founders of computer science and artificial intelligence.
E. An Investigation of the Laws of Thought
An Investigation of the Laws of Thought is George Boole’s foundational 1854 treatise that established Boolean algebra and helped lay the groundwork for modern mathematical logic and computer science.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: Church–Turing thesis
Target entity description: 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).

A. Turing machine
A Turing machine is an abstract computational model that manipulates symbols on an infinite tape according to a set of rules, providing a formal foundation for the concept of algorithm and computability.
B. On Computable Numbers with an Application to the Entscheidungsproblem
"On Computable Numbers, with an Application to the Entscheidungsproblem" is Alan Turing’s landmark 1936 paper that introduced the Turing machine model and founded the formal study of computability and the limits of algorithmic decision procedures.
C. von Neumann architecture
The von Neumann architecture is a foundational computer design model in which a single memory stores both program instructions and data, executed sequentially by a central processing unit.
D. Alan Turing
Alan Turing was a pioneering British mathematician and logician whose foundational work in computing and codebreaking established him as one of the principal founders of computer science and artificial intelligence.
E. An Investigation of the Laws of Thought
An Investigation of the Laws of Thought is George Boole’s foundational 1854 treatise that established Boolean algebra and helped lay the groundwork for modern mathematical logic and computer science.
F. None of above. chosen

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–Deutsch principle ⓘ linked to: Church–Turing thesis extended Church–Turing thesis ⓘ linked to: Church–Turing thesis physical Church–Turing thesis ⓘ linked to: Church–Turing thesis strong Church–Turing thesis ⓘ linked to: 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 ⓘ linked to: Gödel's incompleteness theorems Hilbert’s Entscheidungsproblem ⓘ linked to: 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 ⓘ

How these facts were elicited

Referenced by (27)

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

Alonzo Church → knownFor → Church–Turing thesis ⓘ

subject linked to: Church (surname)

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

subject linked to: On Computable Numbers with an Application to the Entscheidungsproblem

Church–Turing thesis → hasVariant → physical Church–Turing thesis ⓘ

linked to: Church–Turing thesis

Church–Turing thesis → hasVariant → strong Church–Turing thesis ⓘ

linked to: Church–Turing thesis

Church–Turing thesis → hasVariant → extended Church–Turing thesis ⓘ

linked to: Church–Turing thesis

Church–Turing thesis → hasVariant → Church–Turing–Deutsch principle ⓘ

linked to: Church–Turing thesis

Alonzo Church → notableWork → Church–Turing thesis ⓘ

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

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

Entscheidungsproblem → relatedTo → Church–Turing thesis ⓘ

Halting problem → relatedTo → Church–Turing thesis ⓘ

Computability Theory → fieldOfStudy → Church–Turing thesis ⓘ

Computability and Unsolvability → topic → Church–Turing thesis ⓘ

The Universal Computer → about → Church–Turing thesis ⓘ

Hilbert’s tenth problem → relatedTo → Church–Turing thesis ⓘ

physical symbol system hypothesis → relatedTo → Church–Turing thesis ⓘ

physical symbol system hypothesis → relatedTo → physical Church–Turing thesis ⓘ

linked to: Church–Turing thesis

Rice's theorem → relatedTo → Church–Turing thesis ⓘ

Kleene’s normal form theorem → relatedTo → Church–Turing thesis ⓘ

Recursive Functions and Intuitionistic Mathematics → subject → Church–Turing thesis ⓘ

Elements of the Theory of Computation → hasTopic → Church–Turing thesis ⓘ

Hilbert's tenth problem → relatedTo → Church–Turing thesis ⓘ

subject linked to: H10

Davis–Putnam–Robinson–Matiyasevich theorem → relatedTo → Church–Turing thesis ⓘ

Limits on Efficient Computation in the Physical World → relatedTo → Church–Turing thesis ⓘ

Limits on Efficient Computation in the Physical World → relatedTo → extended Church–Turing thesis ⓘ

linked to: Church–Turing thesis

Kleene–Rosser paradox → relatedTo → Church’s thesis ⓘ

linked to: Church–Turing thesis

Theory of Recursive Functions and Effective Computability → topic → Church–Turing thesis ⓘ

All labels observed (6)

How this entity was disambiguated Show

Statements (53)

How these facts were elicited Show

Referenced by (27)

How this entity was disambiguated

How these facts were elicited