Skip to main content

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 True

def 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".

Comments

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

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
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!)
jjinux said…
> I assume you saw the "Dr. Suess" proof of the halting problem on hackernews recently...

Sweet ;)
jjinux 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.
jjinux said…
Now I see the problem:

> 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 ;)
jjinux 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 :)
jjinux said…
> Art Vandalay said...

Agreed.
Anonymous 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.
test said…
Hi everyone, Can you please help me for my python program project which is halting analyzer? It would be great help. Thanks.

Popular posts from this blog

Drawing Sierpinski's Triangle in Minecraft Using Python

In his keynote at PyCon, Eben Upton, the Executive Director of the Rasberry Pi Foundation, mentioned that not only has Minecraft been ported to the Rasberry Pi, but you can even control it with Python. Since four of my kids are avid Minecraft fans, I figured this might be a good time to teach them to program using Python. So I started yesterday with the goal of programming something cool for Minecraft and then showing it off at the San Francisco Python Meetup in the evening.

The first problem that I faced was that I didn't have a Rasberry Pi. You can't hack Minecraft by just installing the Minecraft client. Speaking of which, I didn't have the Minecraft client installed either ;) My kids always play it on their Nexus 7s. I found an open source Minecraft server called Bukkit that "provides the means to extend the popular Minecraft multiplayer server." Then I found a plugin called RaspberryJuice that implements a subset of the Minecraft Pi modding API for Bukkit s…

Apple: iPad and Emacs

Someone asked my boss's buddy Art Medlar if he was going to buy an iPad. He said, "I figure as soon as it runs Emacs, that will be the sign to buy." I think he was just trying to be funny, but his statement is actually fairly profound.

It's well known that submitting iPhone and iPad applications for sale on Apple's store is a huge pain--even if they're free and open source. Apple is acting as a gatekeeper for what is and isn't allowed on your device. I heard that Apple would never allow a scripting language to be installed on your iPad because it would allow end users to run code that they hadn't verified. (I don't have a reference for this, but if you do, please post it below.) Emacs is mostly written in Emacs Lisp. Per Apple's policy, I don't think it'll ever be possible to run Emacs on the iPad.

Emacs was written by Richard Stallman, and it practically defines the Free Software movement (in a manner of speaking at least). Stal…

JavaScript: Porting from react-css-modules to babel-plugin-react-css-modules (with Less)

I recently found a bug in react-css-modules that prevented me from upgrading react-mobx which prevented us from upgrading to React 16. Then, I found out that react-css-modules is "no longer actively maintained". Hence, whether I wanted to or not, I was kind of forced into moving from react-css-modules to babel-plugin-react-css-modules. Doing the port is mostly straightforward. Once I switched libraries, the rest of the port was basically:
Get ESLint to pass now that react-css-modules is no longer available.Get babel-plugin-react-css-modules working with Less.Get my Karma tests to at least build.Get the Karma tests to pass.Test things thoroughly.Fight off merge conflicts from the rest of engineering every 10 minutes ;) There were a few things that resulted in difficult code changes. That's what the rest of this blog post is about. I don't think you can fix all of these things ahead of time. Just read through them and keep them in mind as you follow the approach above.…