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?(adsbygoogle = window.adsbygoogle || []).push({});

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

int main()

{

while (randBool());

return 0;

}

Thenpis inPbut it is impossible to know whetherpruns forever. Therefore it is impossible to create a program that can take every memberPand check for infinite runtime.

Is there anything wrong with my logic?

**Physics Forums - The Fusion of Science and Community**

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

Loading...

Similar Threads - Impossible program tell | Date |
---|---|

I Linear programming problem | Oct 31, 2017 |

How is causality proven when it's impossible to change the IV? | Oct 26, 2012 |

Probability of a random number - seems impossible | Apr 28, 2011 |

Bell's impossibility theorem, equivalence classes: SOS! | Dec 22, 2010 |

An impossible circle? | May 20, 2009 |

**Physics Forums - The Fusion of Science and Community**