Exam-style question
Try this first
A proposed analyser is intended to accept any program and its particular input, then always report whether that program will eventually stop. Explain why this proposal is related to the Halting problem and state what the specification implies about such a general solution.
Model answer
What a good answer should say
- The proposed analyser is attempting to solve the Halting problem because it must determine whether any program will eventually stop for particular input.
- The specification implies that no general computer solution can always solve this problem, because the Halting problem demonstrates that some problems cannot be solved by a computer.
- The analyser might correctly deal with some selected programs and inputs, but it cannot provide a guaranteed answer for every possible case.
Explanation
Why this works
The answer links the proposed analyser to the defining task of the Halting problem and distinguishes between solving individual cases and solving the general problem. The key conclusion is that a guaranteed solution for every program and input is impossible within computation.
Common mistake
No common mistake is linked to this question yet.