A student argues that the halting problem is only unsolvable in practice because computers lack sufficient processing power and memory. What does theory of computation establish?
AThe student is correct; a sufficiently powerful computer could solve the halting problem.
BThe halting problem is mathematically undecidable: no algorithm can solve it for all inputs regardless of computational resources, time, or memory.
CThe halting problem is solvable for most practical programs, just not pathological edge cases.
DQuantum computers can solve the halting problem because they transcend classical computational limits.
Undecidability is a mathematical impossibility, not an engineering limitation. The proof (by diagonalization and contradiction) shows that any algorithm claiming to decide the halting problem leads to a logical contradiction — it cannot exist. No amount of computing power changes this. Quantum computers, parallel processors, and future architectures are all instances of Turing-equivalent models and cannot escape this result.
Question 2 Multiple Choice
How do the three major branches of theory of computation — automata theory, computability theory, and complexity theory — relate to each other conceptually?
AThey study the same problems using different formalisms that happen to give equivalent results.
BThey form a hierarchy of questions: what can be recognized, what can be decided with unlimited resources, and what can be decided efficiently.
CThey describe three different hardware architectures and their respective programming models.
DAutomata theory is a subset of complexity theory, which is a subset of computability theory.
The three branches address successively finer questions. Automata theory asks what languages can be recognized by different machine models (finite automata, pushdown automata, Turing machines). Computability theory asks which problems can be decided at all given unlimited time and memory. Complexity theory asks, among the decidable problems, which can be solved with feasible resources. Together they form a coherent picture of computational power at increasing levels of refinement.
Question 3 True / False
In theory of computation, any computational problem can be reframed as asking whether a given string belongs to a particular set of strings (a formal language).
TTrue
FFalse
Answer: True
This encoding is central to the field. For example, 'does program P halt on input x?' becomes 'does the string ⟨P, x⟩ belong to the halting language?' The language framework lets theorists apply uniform tools — automata, grammars, reductions — to any computational problem, regardless of its surface form.
Question 4 True / False
Saying a problem is undecidable means it is computationally hard — it would take an unreasonably long time to solve on today's computers.
TTrue
FFalse
Answer: False
Undecidability and computational hardness are different concepts. An undecidable problem has no algorithm that solves it correctly for all inputs — not even given infinite time and memory. A computationally hard problem (like an NP-hard problem) has a correct algorithm but requires infeasibly large resources. The halting problem is undecidable; integer factoring is hard but decidable (there is an algorithm — it's just slow).
Question 5 Short Answer
Explain why the halting problem is called 'undecidable' rather than simply 'computationally hard' or 'unsolved.'
Think about your answer, then reveal below.
Model answer: Undecidable means it has been mathematically proven that no algorithm can correctly determine, for every program-input pair, whether execution halts. The proof constructs a contradiction: assume such an algorithm H exists, then build a program D that calls H on itself and does the opposite of what H predicts — D's behavior contradicts H's output no matter what H returns. This is not a limitation of current technology; it is a logical impossibility. 'Hard' problems can still be solved correctly; undecidable ones cannot be solved correctly for all cases, ever.
The distinction matters: complexity classes (P, NP) classify decidable problems by resource use. Undecidability is a prior, absolute barrier — the problem cannot even be placed in any complexity class, because no algorithm exists at all.