The Halting Problem Revisited
- Simulate the first step of the algorithm given.
- If the program halts, return
Yes, the algorithm haltsand terminate.
- If it does not halt (as of yet), capture a snapshot of the simulation.
- Compare the snapshot with the previous snapshots. If it is the same as one of the snapshots previously taken, return
No, the algorithm does not haltand terminate.
- Simulate the next step.
- Go to 2.
Now which of the following is true?
A. The construction is correct; The halting problem is only undecidable for computers with infinite memory
B. The construction is wrong; Snapshots of a simulation cannot be captured by a computer program
C. The construction is wrong; The simulation might run into a previously encountered snapshot but still halt.
D. The construction is correct; It solves the halting problem in general for any computer
E. The construction is wrong; The described construction cannot be written as a finite program in a proper computer.
Note: The construction refers to the algorithm described, which is the one that is supposed to solve the halting problem.