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

- Simulate the first step of the algorithm given.
- If the program halts, return
`Yes, the algorithm halts`

and 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 halt`

and 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.

×

Problem Loading...

Note Loading...

Set Loading...