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 B

Ubuntu 20.04 on a 2015 15" MacBook Pro

I decided to give Ubuntu 20.04 a try on my 2015 15" MacBook Pro. I didn't actually install it; I just live booted from a USB thumb drive which was enough to try out everything I wanted. In summary, it's not perfect, and issues with my camera would prevent me from switching, but given the right hardware, I think it's a really viable option. The first thing I wanted to try was what would happen if I plugged in a non-HiDPI screen given that my laptop has a HiDPI screen. Without sub-pixel scaling, whatever scale rate I picked for one screen would apply to the other. However, once I turned on sub-pixel scaling, I was able to pick different scale rates for the internal and external displays. That looked ok. I tried plugging in and unplugging multiple times, and it didn't crash. I doubt it'd work with my Thunderbolt display at work, but it worked fine for my HDMI displays at home. I even plugged it into my TV, and it stuck to the 100% scaling I picked for the othe

Creating Windows 10 Boot Media for a Lenovo Thinkpad T410 Using Only a Mac and a Linux Machine

TL;DR: Giovanni and I struggled trying to get Windows 10 installed on the Lenovo Thinkpad T410. We struggled a lot trying to create the installation media because we only had a Mac and a Linux machine to work with. Everytime we tried to boot the USB thumb drive, it just showed us a blinking cursor. At the end, we finally realized that Windows 10 wasn't supported on this laptop :-/ I've heard that it took Thomas Edison 100 tries to figure out the right material to use as a lightbulb filament. Well, I'm no Thomas Edison, but I thought it might be noteworthy to document our attempts at getting it to boot off a USB thumb drive: Download the ISO. Attempt 1: Use Etcher. Etcher says it doesn't work for Windows. Attempt 2: Use Boot Camp Assistant. It doesn't have that feature anymore. Attempt 3: Use Disk Utility on a Mac. Erase a USB thumb drive: Format: ExFAT Scheme: GUID Partition Map Mount the ISO. Copy everything from