Impossible to make a program to tell whether a program runs forever

[Jamin2112]

I remember someone telling me that it's impossible to create a program that determines whether a given program runs forever, and that this requires a rigorous and long proof. Well, I was thinking about that today and the proof should be trivial -- shouldn't it?

Proof. Let P be the set of all programs. Let randBool() be a function that returns a random boolean, with it's probability space being uniformly distributed. Let p be the following.

int main()
{
while (randBool());
return 0;
}

Then p is in P but it is impossible to know whether p runs forever. Therefore it is impossible to create a program that can take every member P and check for infinite runtime.

Is there anything wrong with my logic?

 

[jedishrfu]

Its known as the halting problem:

http://en.wikipedia.org/wiki/Halting_problem

With respect to your logic, I think the statement:

Then p is in P but it is impossible to know whether p runs forever.

is the conclusion of the halting problem proof.

Turing proved no algorithm can exist which will always correctly decide whether, for a given arbitrary program and its input, the program halts when run with that input; the essence of Turing's proof is that any such algorithm can be made to contradict itself, and therefore cannot be correct.

 

[alan2]

Others know more about this than I do but my observation is that those random numbers aren't really random so your conclusion, that it's impossible to know if p runs forever, may not be true.

 

[FactChecker]

I believe that the theorem you are interested in proving applies even to the set of programs that are completely deterministic -- nothing random or uncertain allowed.

 

[AlephZero]

I remember someone telling me that it's impossible to create a program that determines whether a given program runs forever,

That's not what Turing was considering. The halting problem is to produce one computer program that can determine whether or not every possible program runs forever. The proof that this is impossible isn't "long", either. But somebody had to be the first person to realize that a "common sense" argument like "you can restructure any computer program into simple logical constructs like sequences of instructions, alternatives, and conditional loops, so there must be a general algorithm to find whether or not it halts" is wrong.

It is almost always possible to prove whether or not a particular program runs forever. Programmers do that all the time when debugging software. For your example, you would need to analyze the code of your randbool() function.

 

[Borek]

I remember someone telling me that it's impossible to create a program that determines whether a given program runs forever, and that this requires a rigorous and long proof.

Check Penrose's The Large, the Small and the Human Mind. He explains Goedel theorem using programs that say whether another program will ever end (theoretical construct only).

Sounds to me like what you have heard can be a misunderstood/twisted interpretation of the chapter from the book.

 

[Jamin2112]

That's not what Turing was considering. The halting problem is to produce one computer program that can determine whether or not every possible program runs forever.

That's what I meant. Poorly stated by me.

 

[Incnis Mrsi]

Jamin2112: algorithms (considered in theory of computation and mathematical logic) are deterministic and may not use random data. Your reasoning, really, has nothing to do with Turing’s halting problem.

 

[cosmik debris]

jamin2112: Algorithms (considered in theory of computation and mathematical logic) are deterministic and may not use random data. Your reasoning, really, has nothing to do with turing’s halting problem.

np, pp, bqp?

 

[Incnis Mrsi]

Yes, Ī said a confusing thing (NP uses some random data, although not probabilistic).

Cosmik debris: please, don’t use text-mangling scripts or browser extensions when quote a post of another user. Ī’m upset to see myself misquoted in such ridiculous way. It is possibly some mobile application, but such nasty feature must be switchable off, otherwise it’s a bug.

 

[Erland]

Turing's argument is very simple, really, and there is no need to use a random generator.

The claim is that there is no program P(x,y), with input x and y, where x is (the code) of an arbitrary program, a y is an arbitrary input string, such that P(x,y) outputs "yes" if the program (with code) x halts on input y, and "no" otherwise.

To prove that no such program P(x,y) exists, assume that it does exist. Then, one can easily construct a program Q(x), with input string x, such that

i) Q(x) goes into a loop if P(x,x) outputs "yes" (i.e. the program with code x halts on input x),
ii) Q(x) halts if P(x,x) outputs "no" (i.e. if the program with code x does not halt on input x).

Now Q(x) has a code, call it c.

Now, does Q(c) halt or not, (i.e. does Q halt on input c)?

Assume that Q(c) halts. Since c is the code of Q, this means that P(c,c) outputs yes. But then, by i), Q(c) goes into a loop, so it does not halt.
So Q(c) halts ==> Q(c) does not halt.

Assume instead that Q(c) does not halt. This means that P(c,c) outputs "no". Then, by, ii), Q(c) halts.
So, Q(c) does nor halt ==> Q(c) halts.

Together, this means that Q(c) halts <==> Q(c) does not halt. This is a contradiction.
It follows that such a program P(x,y) does not exist.

 

[stevendaryl]

Jamin2112: algorithms (considered in theory of computation and mathematical logic) are deterministic and may not use random data. Your reasoning, really, has nothing to do with Turing’s halting problem.

You're right, but there is a sense in which Turing's result implies that there are mathematically well-defined numbers that will appear completely random to any computer program. Chaitin's constant $\Omega$, which you can think of roughly as the probability that a randomly generated computer program will halt, appears random, in the sense that no computer program can compute more than some finite number of decimal places of it.

 

[cosmik debris]

Yes, Ī said a confusing thing (NP uses some random data, although not probabilistic).

Cosmik debris: please, don’t use text-mangling scripts or browser extensions when quote a post of another user. Ī’m upset to see myself misquoted in such ridiculous way. It is possibly some mobile application, but such nasty feature must be switchable off, otherwise it’s a bug.

Well you said "algorithms (considered in theory of computation and mathematical logic) are deterministic and may not use random data."

I thought the N in NP stood for non-deterministic. The other classes I mentioned are probabilistic. They are all considered in theories of Computer Science.

As for the quote thing, I just it the quote button at the bottom of the post.

 

[HallsofIvy]

You're right, but there is a sense in which Turing's result implies that there are mathematically well-defined numbers that will appear completely random to any computer program. Chaitin's constant $\Omega$, which you can think of roughly as the probability that a randomly generated computer program will halt, appears random, in the sense that no computer program can compute more than some finite number of decimal places of it.

That is NOT what "random" means!

 

[Mark44]

The original quote.

Jamin2112: algorithms (considered in theory of computation and mathematical logic) are deterministic and may not use random data. Your reasoning, really, has nothing to do with Turing’s halting problem.

cosmik debris's "mangled" quote of the above.

jamin2112: Algorithms (considered in theory of computation and mathematical logic) are deterministic and may not use random data. Your reasoning, really, has nothing to do with turing’s halting problem.

Cosmik debris: please, don’t use text-mangling scripts or browser extensions when quote a post of another user. Ī’m upset to see myself misquoted in such ridiculous way. It is possibly some mobile application, but such nasty feature must be switchable off, otherwise it’s a bug.

Incnis Mrsi,
The only differences I see between what you wrote and what cosmik debris "quoted" was capitalizing "algorithms" and neglecting to capitalize "turing". IMO, this hardly qualifies as being misquoted in a "ridiculous way." It should have been copied verbatim, I agree, but chill out on the indignance.

cosmik debris,
When you quote someone, take more care to get what you're quoting exactly right.

Edit: It might be that you (Incnis Mrsi) are using some browser extension that causes quoted text to display differently in other browsers. For example, the mentors have noticed that you type "Ī" with a bar over it. What's up with that?

 

[cosmik debris]

The original quote.

cosmik debris's "mangled" quote of the above.



Incnis Mrsi,
The only differences I see between what you wrote and what cosmik debris "quoted" was capitalizing "algorithms" and neglecting to capitalize "turing". IMO, this hardly qualifies as being misquoted in a "ridiculous way." It should have been copied verbatim, I agree, but chill out on the indignance.

cosmik debris,
When you quote someone, take more care to get what you're quoting exactly right.

Edit: It might be that you (Incnis Mrsi) are using some browser extension that causes quoted text to display differently in other browsers. For example, the mentors have noticed that you type "Ī" with a bar over it. What's up with that?

Yeah sorry, all I did was hit the quote button, it may be my browser or something but it certainly was not intentional.