Science Forums 2

[Kriminal99]

Originally Posted by phillip1882

the halting problem is not saying you can't determine whether a particular program will halt.
its saying there's no universal program to determine whether any program will halt.
let me show you what i mean.

let's say we have the program

x =0
while x <10:
   x = x+1
   x = x-1

and want an algorithm to determine whether or not this program will halt. we note that x goes back and forth between two numbers 0, and 1. so one possible algorithm would be
if x value resets, the program will never halt.
now however consider

y = 0
while x <10:
   y=y+1
   x = 0
   x = y

the x value resets every iteration, but then quickly goes to the value y. so we need a new algorithm. one possible algorithm would be, if x repeats its pattern, the program will never halt.
now consider

y = 0
while x <10:
    y = y+1
    x = 0
    x = 1
    if y = 10:
       x = 11

x repeats its pattern 10 times, yet the program still halts.
in short there is no algorithm that will guarantee an accurate halt detection.

Hey. There is a common thread in each of the programs that loop forever that is not in the program that does halt. Namely, there is a complete state or configuration that repeats. At one point, the program is at the same point with the same value for the variables. This is clear evidence of an infinite loop.

In the final code, this is not the case because y has a different value in each iteration.

There is another kind of infinite loop where values change, but they never go in a direction that will allow the program to halt. This is also easily detectable.

I suppose the most difficult question is to ask how does one know that a program that takes N steps toward a ending value (x - n; if (x < 10) {quit;} else {x + n + m;}) then M steps back halts or not in general.