Beta. Content is under active construction and has not been peer-reviewed. Report errors on
GitHub
.
Disclaimer
Theorem
Path
Curriculum
Paths
Demos
Diagnostic
Search
Quiz Hub
/
Computability Theory
Computability Theory
4 questions
Difficulty 4-10
View topic
Intermediate
0 / 4
3 intermediate
1 advanced
Adapts to your performance
1 / 4
intermediate (4/10)
state theorem
The halting problem asks whether a given program halts on a given input. Turing proved it is undecidable. What does this mean?
Hide and think first
A.
The halting problem requires infinite memory to even formulate, making it undefined in practice
B.
Computers cannot simulate programs because doing so requires deciding halting in advance
C.
No algorithm can decide, for every program-input pair, whether the program halts
D.
No algorithm can decide, for any single program-input pair, whether that specific pair halts
Submit Answer