Tip:
Highlight text to annotate it
X
All right. Infinite loops, those are no fun at all.
I want to see my web page.
I don't want to wait an infinite number of seconds and then see my web page.
That's pretty long. I would get hungry before that ran out.
Wouldn't it be nice if we could just tell if a program was going to loop forever or not?
And then if it's going to loop forever, I won't run it or I'll print a little warning on the web page,
but I won't waste a lot of time on it.
So what I'd really like to do is just look at the program source code
as we got it from the Web, say, and just be able to tell if it loops forever
in one of these infinite loops or if it halts, if it stops,
if it settles down and returns an answer after some finite amount of time.
This seems like a totally legitimate request.
Unfortunately, it's not just difficult, it's actually impossible, provably impossible.
Not really hard, we're too lazy, we couldn't figure it out,
but we know you can't do it.
You can't make this determination correctly every time.
To see why this can't happen, let's assume we could solve it
and see what bad things happen to the world.
Let's assume that we have thought very hard about this
and we have somehow implemented a magic procedure called halts
which takes another procedure as an argument and returns True if that procedure halts
and False if it loops forever.
Now we'd know if it's safe to evaluate a web page.
We just look at all the JavaScript on the web page, we call halts on it,
if that returns True every time, we can totally render that web page.
Let's test our understanding of this mythical halts procedure.
Over here on the left I've written 4 bits of Python code:
vladimir, nabokov, pale, and fire,
and fire is in red because that's warm.
One possibility is that we think vladimir halts;
another possibility is that we think nabokov halts.
What I'd like you to do is tell me which of these 4 statements--
there could be multiple--are actually true.
Check each box that corresponds to a true fact.