Church–Turing thesis

All labels observed (5)

Label	Occurrences
Church–Turing thesis canonical	12
physical Church–Turing thesis	2
Church–Turing–Deutsch principle	1
extended Church–Turing 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 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 ⓘ

How these facts were elicited

Referenced by (17)

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

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

subject surface form: Alonzo Church

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

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

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 ⓘ

this entity surface form: physical Church–Turing thesis

All labels observed (5)

How this entity was disambiguated Show

Statements (53)

How these facts were elicited Show

Referenced by (17)

How this entity was disambiguated

How these facts were elicited