Consider the following algorithm which when fed with another algorithm and an input, tells if the program halts:
Yes, the algorithm halts
and terminate.No, the algorithm does not halt
and terminate.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.