Exam-style question
Try this first
Describe the Halting problem and explain why it is important for the theory of computation.
Model answer
What a good answer should say
- The Halting problem is the problem of determining whether any program will eventually stop when it is given particular input.
- It is important because it demonstrates that there are some problems that cannot be solved by a computer.
- Therefore, increasing the computer's speed or writing a more detailed program cannot guarantee a solution for every possible program and input.
Explanation
Why this works
A complete answer identifies the problem as deciding whether a program eventually stops for particular input and then explains its significance: some problems are unsolvable by computer. The answer should focus on the limit of computation rather than on program efficiency.
Common mistake
No common mistake is linked to this question yet.