## Saturday, May 08, 2010

### 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:
`def does_stop():    return Truedef does_not_stop():    while True:        pass`
does_stop does stop. does_not_stop does not stop. How do I implement the following function:
`def will_stop(f):    """Return True if the function f eventually stops, and False otherwise."""    ...`
Let's suppose for a moment that I can implement such a function. Now, let's look at this function:
`def just_might_stop():    return will_stop(just_might_stop) and does_not_stop()`
Does just_might_stop stop or does it continue forever? That is, what is the value of "will_stop(just_might_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".

metapundit.net said...

I assume you saw the "Dr. Suess" proof of the halting problem on hackernews recently...

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

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;

Aldrin Martoq said...

I think there is a fault in your logic:

<<>>

But, from the definition:
def just_might_stop():
return will_stop(just_might_stop) and does_not_stop()

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

private said...

This is an example of NP-hard problem that is not NP-complete. This Wikipedia article is a good source and alos This lecture notes for computer science class.

Art Vandalay said...

Of course, while a total solution to the generalized halting problem is impossible, lesser solutions can work pretty well in concrete cases. Static analysis can be a great time-saver!

(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!)

Shannon -jj Behrens said...

> I assume you saw the "Dr. Suess" proof of the halting problem on hackernews recently...

Sweet ;)

Shannon -jj Behrens said...

> I think there is a fault in your logic:

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.

Shannon -jj Behrens said...

Now I see the problem:

> But, from the definition:
def just_might_stop():
return will_stop(just_might_stop) and does_not_stop()

Remember that does_not_stop() won't even be executed if will_stop(just_might_stop) returns False. It's a trick ya see ;)

Shannon -jj Behrens said...

> This is an example of NP-hard problem that is not NP-complete. This Wikipedia article is a good source and alos This lecture notes for computer science class.

Thanks for the reference :)

Shannon -jj Behrens said...

> Art Vandalay said...

Agreed.

Nicolai Mork, Editor-in-Chief, Award Winning Journalist said...

When you first see a problem like this, it's hard not to think, 'this is just a silly gimmick, a word game.' But I found my mind kept returning to the old one 'I always lie.' I was interested to find a lot of references to it in the fiction of David Foster Wallace and relevant ideas in linguistic philosophy as well. I stumbled on your website because I'm trying to learn python; it was fun to see it represented in python!

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.