The Halting Problem Revisited

Computer Science Level 4

Consider the following algorithm which when fed with another algorithm and an input, tells if the program halts:

  1. Simulate the first step of the algorithm given.
  2. If the program halts, return Yes, the algorithm halts and terminate.
  3. If it does not halt (as of yet), capture a snapshot of the simulation.
  4. 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 halt and terminate.
  5. Simulate the next step.
  6. 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.


Problem Loading...

Note Loading...

Set Loading...