Python: The Halting Problem
I've been reading The Little Schemer, and I particularly enjoyed learning about the halting problem. I enjoyed learning about it so much that I figured I'd take the time to explain it in Python so that other Pythonistas could enjoy it with me ;)
Let's suppose I have two functions:
Well, I don't know yet, but let's suppose that "will_stop(just_might_stop)" returns True, i.e. that just_might_stop does stop. Well, looking at the definition of just_might_stop, it should "return will_stop(just_might_stop) and does_not_stop()". Since we stipulated that "will_stop(just_might_stop)" is True, then the function will execute "does_not_stop()", and hence, just_might_stop will never stop.
This time, let's suppose that "will_stop(just_might_stop)" returns False, i.e. that just_might_stop does not stop. Looking at the definition of just_might_stop, it should "return will_stop(just_might_stop) and does_not_stop()", i.e. it should return False. However, that means that just_might_stop did stop, even though we stipulated that "will_stop(just_might_stop)" returns False.
It turns out that whether will_stop(just_might_stop) returns True or False, it still leads to a contradiction. Hence, it turns out that it's not possible to implement will_stop.
Fun, huh? It's yet another version of "this statement is false".
Let's suppose I have two functions:
def does_stop():does_stop does stop. does_not_stop does not stop. How do I implement the following function:
return True
def does_not_stop():
while True:
pass
def will_stop(f):Let's suppose for a moment that I can implement such a function. Now, let's look at this function:
"""Return True if the function f eventually stops, and False otherwise."""
...
def just_might_stop():Does just_might_stop stop or does it continue forever? That is, what is the value of "will_stop(just_might_stop)"?
return will_stop(just_might_stop) and does_not_stop()
Well, I don't know yet, but let's suppose that "will_stop(just_might_stop)" returns True, i.e. that just_might_stop does stop. Well, looking at the definition of just_might_stop, it should "return will_stop(just_might_stop) and does_not_stop()". Since we stipulated that "will_stop(just_might_stop)" is True, then the function will execute "does_not_stop()", and hence, just_might_stop will never stop.
This time, let's suppose that "will_stop(just_might_stop)" returns False, i.e. that just_might_stop does not stop. Looking at the definition of just_might_stop, it should "return will_stop(just_might_stop) and does_not_stop()", i.e. it should return False. However, that means that just_might_stop did stop, even though we stipulated that "will_stop(just_might_stop)" returns False.
It turns out that whether will_stop(just_might_stop) returns True or False, it still leads to a contradiction. Hence, it turns out that it's not possible to implement will_stop.
Fun, huh? It's yet another version of "this statement is false".
Comments
Pretty awesome:
Well, the truth is that P cannot possibly be,
because if you wrote it and gave it to me,
I could use it to set up a logical bind
that would shatter your reason and scramble your mind.
Here’s the trick I would use – and it’s simple to do.
I’d define a procedure – we’ll name the thing Q -
that would take any program and call P (of course!)
to tell if it looped, by reading the source;
<<>>
But, from the definition:
def just_might_stop():
return will_stop(just_might_stop) and does_not_stop()
Because does_not_stop() doesn't stop, we already know just_might_stop doesn't stop instead of your supposition.
From a more practical view, you can implement a function that returns:
a) TRUE: it can precisely determine if F will stop.
b) FALSE: it can precisely determine if F will not stop.
c) NONE: it cannot precisely determine if F will stop or not.
This could be far more useful (ex: take the NONE case as the FALSE case). And this can be written in python, see the following code as a start. It does not implement the FALSE case, but this kind of cases can be analyzed just as eclipse does in java... simple cases like a while True: pass, we can check recursively if the called functions will_stop or not, if there is a loop in the calling tree, etc.
#!/usr/bin/env python
def does_stop():
return True
def does_not_stop():
while True:
pass
def calling():
does_stop()
does_not_stop()
def will_stop(F):
"""Returns:
True: it can precisely determine if F will stop
False: it can precisely determina if F will not stop
None: it cannot precisely determine if F will stop or not"""
import dis,sys,cStringIO
oldstdout = sys.stdout
sys.stdout = cStringIO.StringIO()
dis.dis(F)
s = sys.stdout.getvalue()
sys.stdout = oldstdout
#print F.__name__, s
if "LOOP" in s: print "%20s: %5s, I'm not sure (LOOP detected)" % (F.__name__, None)
return None
if "CALL_" in s:
print "%20s: %5s, I'm not sure (CALL detected)" % (F.__name__, None)
return None
print "%20s: %5s, I'm sure it does stop" % (F.__name__, True)
return True
will_stop(does_not_stop)
will_stop(calling)
will_stop(does_stop)
---------
$ python t.py
does_not_stop: None, I'm not sure (LOOP detected)
calling: None, I'm not sure (CALL detected)
does_stop: True, I'm sure it does stop
(Although when someone has a highly-dynamic or meta- program whose final form will only appear at execution time, static analysis is useless to address the halting problem. If one must run the code to understand it, then there's no guarantee your "executing parser" itself will halt!)
Sweet ;)
Maybe, but probably not. I'm just translating some stuff from a famous book to Python. By the way, don't forget that "and" short circuits in Python.
> But, from the definition:
def just_might_stop():
return will_stop(just_might_stop) and does_not_stop()
> Because does_not_stop() doesn't stop, we already know just_might_stop doesn't stop instead of your supposition.
Remember that does_not_stop() won't even be executed if will_stop(just_might_stop) returns False. It's a trick ya see ;)
Thanks for the reference :)
Agreed.
I classify these as 'subject-object paradoxes.' Language implicitly assumes some degree of separation between itself and what it describes. So it can be reduced to absurdity by these sorts of recursive situations. Again, a game, but: people are intensely communicative. Often times what is said is meant to be a representation of the speaker. This creates profound problems. A person can spend a lifetime stuck in some of these recursions of self-definition.