Tip:
Highlight text to annotate it
X
This was potentially a difficult quiz, requires you to think about outside the box
of what I normally ask.
We can implement optimization okay so that it returns a safe answer for optimization in all cases.
Remember how are we using optimization okay?
We consider a bunch of optimizations, and if this says True, then we swap out parts of the program.
A safe answer is just to return false all the time,
never do any optimization.
That'll make for a slower programs, but it's safe because we'll always get the same answer.
We're never changing the meaning of the program.
Optimization is sometimes described as conservative because if you're not
absolutely certain that an optimization is okay, just be conservative and don't do it,
and you'll be fine. The program will be a little slower, but it'll always get the right answer.
We cannot implement and optimization okay that works precisely in all cases.
It is undecidable like the Halting Problem.
This sadly is true.
I'm going to sketch an answer for this.
A formal proof that something is impossible, like the Halting Problem,
is a little beyond the scope of most of this class.
But let me show you how it would go.
Suppose we could write optimization okay in a way that was
precisely correct in all cases.
I, the Great Wesini, shall solve the Halting Problem
by telling you if an arbitrary program halts or not.
You want to know if a program P halts or not.
I'm going to tell you how to do it.
Remember, we know this is impossible.
Here's how we do it.
Suppose you claim we've implemented optimizationok.
It always gets exactly the right answer.
I'm going to use it to build a Halting Problem solver.
You give me a program P and you want to know if it halts?
I just make up a little program over here called "loops forever" or "loops."
This procedure loops sets x to zero and while True, it increments x.
We've seen before that this program never terminates, never returns a value.
I can just check to see if your program ever halts by checking to see if it would be
okay to replace it with loops forever.
If your program gets the same answer on all inputs as loops forever,
then your program loops forever on all inputs.
Otherwise, your program halts.
If optimizationok could be written, then the Halting Problem could be written--
this Halting Problem decider. But this cannot be.
We've seen before that there is no way to solve the Halting Problem.
It's equivalent to figuring out if "this sentence is false" is true or false.
It's a contradiction in the real world.
So halts is impossible, but I could totally make halts if I had optimizationok.
That means optimizationok must me impossible--impossible to solve every time precisely.
We can solve it some of the time. We just can't solve it all of the time.
Because if we could solve it all of the time, it'd be just like the Halting Problem.
Then finally down here at the end--
optimizationok of AB implies optimizationok of BA.
This is true because we're just checking equality.
If A = B, then B = A.
Now the two I've picked--George F Will, a Pulitzer Prize-winning conservative commentator,
and Betty Frieden who wrote The Feminine Mystique
and lead second-wave feminism in the United States--
they're unlikely to have exactly the same things to say.
These two are unlikely to be equal, but if they were
then you could reverse it, and they would match up. You never know. Check them both out.