Halting problem
E143342
The halting problem is a fundamental decision problem in computability theory that asks whether a given program will eventually stop running or continue to run forever, and is famously proven to be undecidable.
All labels observed (2)
| Label | Occurrences |
|---|---|
| Chaitin's constant | 1 |
| Halting problem canonical | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T1255211 — 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: Halting problem Context triple: [Church–Turing thesis, relatesToConcept, Halting problem]
-
A.
Entscheidungsproblem
The Entscheidungsproblem is a foundational decision problem in mathematical logic that asks whether there exists a general algorithm to determine the truth or falsity of any given first-order logical statement.
-
B.
Church–Turing thesis
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).
-
C.
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.
-
D.
Gödel's incompleteness theorems
Gödel's incompleteness theorems are two fundamental results in mathematical logic showing that any sufficiently powerful, consistent formal system cannot prove all true statements about arithmetic, and cannot prove its own consistency.
-
E.
P versus NP problem
The P versus NP problem is a central unsolved question in theoretical computer science that asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.
- 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: Halting problem Target entity description: The halting problem is a fundamental decision problem in computability theory that asks whether a given program will eventually stop running or continue to run forever, and is famously proven to be undecidable.
-
A.
Entscheidungsproblem
The Entscheidungsproblem is a foundational decision problem in mathematical logic that asks whether there exists a general algorithm to determine the truth or falsity of any given first-order logical statement.
-
B.
Church–Turing thesis
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).
-
C.
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.
-
D.
Gödel's incompleteness theorems
Gödel's incompleteness theorems are two fundamental results in mathematical logic showing that any sufficiently powerful, consistent formal system cannot prove all true statements about arithmetic, and cannot prove its own consistency.
-
E.
P versus NP problem
The P versus NP problem is a central unsolved question in theoretical computer science that asks whether every problem whose solution can be quickly verified by a computer can also be quickly solved by a computer.
- F. None of above. chosen
Statements (50)
| Predicate | Object |
|---|---|
| instanceOf |
decision problem
ⓘ
problem in computability theory ⓘ undecidable problem ⓘ |
| appliesTo |
Turing-complete programming languages
ⓘ
abstract machine models equivalent to Turing machines ⓘ |
| asks |
whether a given program halts on a given input
ⓘ
whether a given program runs forever on a given input ⓘ |
| cannotBe | decided by any single algorithm for all program–input pairs ⓘ |
| concerns |
Turing machine
ⓘ
surface form:
Turing machines
behavior of algorithms ⓘ |
| doesNotApplyTo | finite-state machines in the same way ⓘ |
| field |
computability theory
ⓘ
mathematical logic ⓘ theoretical computer science ⓘ |
| formalizedAs |
membership problem for the halting set K
ⓘ
set of indices of Turing machines that halt on a given input ⓘ |
| hasComplexityClass | not decidable in any classical time or space complexity class ⓘ |
| hasConsequence |
no algorithm can detect all infinite loops
ⓘ
no perfect general-purpose program verifier exists ⓘ |
| hasEncoding | as a yes–no decision problem ⓘ |
| hasNotation |
HALT
ⓘ
K ⓘ |
| hasProperty |
undecidable
ⓘ
unsolvable by any general algorithm ⓘ |
| hasVariant |
termination problem in program analysis
ⓘ
totality problem ⓘ |
| implies |
existence of undecidable problems in arithmetic
ⓘ
limits of algorithmic computation ⓘ |
| influenced |
development of program verification
ⓘ
philosophy of computation ⓘ theory of formal methods ⓘ |
| introducedInWork |
On Computable Numbers with an Application to the Entscheidungsproblem
ⓘ
surface form:
On Computable Numbers, with an Application to the Entscheidungsproblem
|
| isCompleteFor | recursively enumerable sets under many-one reduction ⓘ |
| proofTechnique |
diagonalization
ⓘ
reduction ad absurdum ⓘ self-reference ⓘ |
| proofYear | 1936 ⓘ |
| provenBy | Alan Turing ⓘ |
| relatedTo |
Church–Turing thesis
ⓘ
Entscheidungsproblem ⓘ Gödel's incompleteness theorems ⓘ Rice's theorem ⓘ Turing degree of the halting set ⓘ computable functions ⓘ partial computable functions ⓘ |
| solutionSet | recursively enumerable but not recursive ⓘ |
| solutionType | no total computable function decides it ⓘ |
| standardFormulation | Given a description of a program and an input, decide whether the program eventually halts when run on that input ⓘ |
| usedIn |
proofs of undecidability of other problems
ⓘ
reductions in computability theory ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Halting problem Description of subject: The halting problem is a fundamental decision problem in computability theory that asks whether a given program will eventually stop running or continue to run forever, and is famously proven to be undecidable.
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
Chaitin's constant