The Halting Problem Revisited

Computer Science Level 2

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.

B E D A C

View wiki
Agnishom Chattopadhyay by Agnishom Chattopadhyay , 22, India

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

The halting problem is only unsolvable for programs which are running on computers with infinite memory.

However, that does not mean we could use the given algorithm for al practical purposes. The memory required to save all the snapshots would be enormous!

4 Helpful 1 Interesting 0 Brilliant 1 Confused

Let me make the point that Turing's Halting problem isn't meant to address a "practical problem", although it originated as one. The analogy is Godel's Incompleteness Theorem, which states that we don't have the assurance of existence a proof or disproof of any given conjecture. How much time or space is practically available for it is not a consideration.

One practical consequence of Turing's Halting problem is that, given a computer program, we may never know if it's completely bug-free, even if given infinite time and memory to make the determination.

Michael Mendrin - 6 years, 1 month ago

The answer implies that the halting problem is somehow solvable if memory is finite? I disagree, when the simulator runs out of memory, we only know that the simulator halts. But we know nothing about the algorithm that was simulated. We will only know that "it was not decided in N steps whether the algorithm halts".

Juraj Variny - 4 years, 3 months ago

Log in to reply

This is like being given a random list of numbers, all of them being even except for maybe one odd one. What does it take to "prove" that there is at least one odd number? The only way that can be determined is to look through all of them, and that's how it's "solved". But, of course, mathematics likes proofs that requires less effort, and considers that "solving".

Michael Mendrin - 4 years, 3 months ago

imagine a very simple program:

c=1

while c!=0: 

 c+=1

This never halts and never returns to a previous state so your program would run infinitely and never reach a decision as to weather this halts or not.

William Whitehouse - 4 years, 9 months ago

Log in to reply

In short: the construction will or will not work on your program depending on how it is implemented:

  • If c is represented using a 32-bit integer, then when it overflows, for example, the program would eventually return to a previous state, and the construction will halt.

  • There are libraries for arbitrary-sized integers. They work by changing the format every time they are about to overflow. So that should avoid this problem, shouldn't it? Say c is implemented using an arbitrary-sized integer. If we do this, the integer must consume some more memory whenever the range of values it represents increases (so that it can still identify the difference between the very first value and the current one, and every one in between). Because the value of c continually increases forever, the program would require infinite memory to complete. In that case the construction would not halt, like you said. Adding true arbitrary-sized integers, due to their nature, causes the program to become capable of using arbitrary (or infinite, unbounded) amounts of memory. This is a fundamentally different class of program. But note that true arbitrary-sized integer libraries can't exist in real life, because they'd need to have a way to construct their arbitrarily-large memory.

So the construction is applicable to any program that takes bounded memory, of which are all the programs that the halting problem can be solved for, and invalid for any other. This is all real-life, constructible programs, but not necessarily all logically-constructable programs, like the one ("G") described in the main article.

But I think the choices need rewording. The construction can be interpreted as both "correct" and "incorrect", as it works for programs with bounded memory, but not in the general case of programs with unbounded memory, which is the set of programs that the halting problem is usually applied to. In that sense, A, B and E could all be considered right (I'm not sure how C could be right, and D is certainly wrong if "in general" includes programs with unbounded memory) (though A is still the one I'd choose).

Ben Jones - 4 years, 3 months ago

Log in to reply

hey william thats what it explains...that it will be in infinite loop

Nandkishor Nangre nandkishorn - 3 years, 7 months ago

I agree with Juraj Variny. The correct answer here implies that the halting problem is decidable with a finite memory, which in turn would mean "In the end all programs will halt due to memory error", which is kind of contradictory with the subject at hand

Juan Zuluaga - 2 years, 9 months ago

In this problem this means that have algorithm is having only finite lines in it?Is am i correct?

Harsh Yadav - 2 years, 9 months ago

Is it possible that the author made a typo? The explanation makes more sense to me, when I replace 'infinite' here in this context with 'finite'. It's also in line with other comments and code-examples that have been shared. But since Turing machines have infinite memory, this program should ideally run on a Turing machine, thereby solving the Halting Problem which we just proved is a unsolvable. I'm more confused now. :|

Ishank Bhardwaj - 2 weeks, 3 days ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...