Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Aug 28, 2014 #1
    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?
  2. jcsd
  3. Aug 28, 2014 #2


    Staff: Mentor

    Its known as the halting problem:


    With respect to your logic, I think the statement:

    is the conclusion of the halting problem proof.

  4. Aug 28, 2014 #3
    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.
  5. Aug 28, 2014 #4


    User Avatar
    Science Advisor
    Gold Member
    2017 Award

    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.
  6. Aug 28, 2014 #5


    User Avatar
    Science Advisor
    Homework Helper

    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.
    Last edited: Aug 28, 2014
  7. Aug 29, 2014 #6


    User Avatar

    Staff: Mentor

    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.
  8. Aug 29, 2014 #7
    That's what I meant. Poorly stated by me.
  9. Sep 3, 2014 #8
    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.
  10. Sep 3, 2014 #9
    np, pp, bqp?
  11. Sep 4, 2014 #10
    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.
    Last edited: Sep 4, 2014
  12. Sep 4, 2014 #11


    User Avatar
    Science Advisor

    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.
  13. Sep 4, 2014 #12


    User Avatar
    Staff Emeritus
    Science Advisor

    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 [itex]\Omega[/itex], 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.
  14. Sep 4, 2014 #13
    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.
  15. Sep 5, 2014 #14


    User Avatar
    Science Advisor

    That is NOT what "random" means!
  16. Sep 5, 2014 #15


    Staff: Mentor

    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?
  17. Sep 7, 2014 #16
    Yeah sorry, all I did was hit the quote button, it may be my browser or something but it certainly was not intentional.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook