Wachowski Brothers used the Halting Problem in the Matrix
Monday, September 19, 2011 12:15:03 AM
Given a description of a computer program, decide whether the program finishes running or continues to run forever. This is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will run forever.
The halting state isn't what's important. The decision problem can be asked about ANY behaviour. In the Matrix, everyone can be thought of a program. This was a central theme and the scene where Morpheus shows Neo what the Matrix is demonstrates quite clearly that we are people who take in inputs and act according to those impulses.
The entire Matrix movie is about showing how the Halting Problem Proof is flawed. Or rather, what it really means.
There was a point in the movie that always stuck with me. It was the scene where Neo goes in to talk to the Oracle and she says, "Don't worry about the vase." and then Neo knocks it over. The Oracle's response was fantastic. She says,
Ohh, what's really going to bake your noodle later on is, would you still have broken it if I hadn't said anything?
And in one simple sentence, the Wachowski Brothers have completely blown apart the halting problem proof.
The Oracle is saying right then and there that no matter what I tell you, I know your future and can control it. The Halting Problem OTOH forces the Oracle to tell Neo exactly what she thinks he will do causing a contradiction.
If she tells Neo that he IS the one, then he will somehow mess it up. Maybe he'll carry too high a burden and not be able to live up to it. Whatever the case, the Oracle knows that telling him the truth will only cause him to go in the opposite direction. Classic case of the "contradiction" program. So she tells him a lie. That he is NOT the one. He will then do the opposite and will find that he is indeed the one. It's almost as if being the ONE is about determination, not of being chosen. It's a whole new level of depth to the Matrix that I never thought about before.
It all culminated with the ultimate decision problem.
In the one hand you'll have Morpheus' life and in the other hand you'll have your own.
Basically, the Oracle turned the tables on Neo. The entire point of the deceiver program used in the Halting Problem Proof is to make no decisions and wait for the Oracle to do it. The Matrix movie addressed this as well.
Oracle: Sorry, kid. You got the gift, but it looks like you're waiting for something.
Oracle: Your next life, maybe. Who knows? That's the way these things go.
So instead, she forced Neo to make a decision. Without a decision, there is no Oracle. There is no future.
What's really baking my noodle though is that the Oracle actually told Neo the truth about being the ONE. Forget if he always was the one or became the one. The point is that the Oracle knew that he would be the one. Yet she said no to Neo. How can that be the truth? Well, it's about interpretations. She knew that the "no" she told Neo meant "yes" to her. She also knew that as long as Neo doesn't make his own decision, she has nothing to go on because an Oracle cannot make decisions for others. They can only report it. He's "waiting" on something, on the Oracle or others to make decisions for him. That's the entire point of the theme behind the Matrix movie. It's also the biggest flaw in the Halting Problem Proof. What's funny is that she actually tells Neo what he's waiting for. His next life when he gets killed at the end.
Suppose you altered the Halting Problem in such a way that you can keep an internal translation table as to what the output from the Oracle really means. All of a sudden, the Halting Problem Proof falls apart.
Over the years, I've gotten a lot of complaints that I don't understand the Halting Problem. People have tried to convince me of this or that. I want to state here and now that I'm in agreement with the experts in the field on this. And they agree with me. Everything about the Halting Problem is about interpretation and definitions. It is NOT about computability. It does not mean you cannot predict how a program will behave. At its narrowest interpretation, it means that you cannot always tell something to a program as to how it will behave using the same domain as what that program understands. IOW, if you tell it that it will go left, then you cannot guarantee that it won't go right. But nothing stops you from knowing how it will behave. You can tell it it will go left because you KNOW that it will go right. You've computed its behaviour. You know it. So it's not about computability. It's about what you can tell the program itself. And this should explain why the Oracle told Neo the opposite.
To recap, the vase scene is the Oracle making a decision FOR Neo. This is the classic Halting Problem Proof, but in reverse. It's where the Oracle makes the decision and then the input program acts on it. What I like is that the indeterminate nature of the Halting Problem in the Halting Problem Proof happens regardless if there is a contradiction or not. In this fine example, Neo's action was not of his own. The Oracle had to make something up. If she says something, Neo knocks over the vase. If she says nothing, nothing happens. It's still indeterminate, because none of this is based on Neo's actions. It's all based on the Oracle initiating the chain of events. And the Halting Problem is based on this. The Wachowski Brothers seem to be shouting this fact to the viewers that understand it.
And finally, the Oracle tells Neo that he is not the one so that he may be the one because she understands that he is the deceiver program. He is the contradiction. It was apparent right from the beginning when Agent Smith captures Neo and Neo does the opposite of everything Smith wants him to do. In fact, he's reluctant to do anything that anyone tells him. NO... WAY! NO... WAY! His almost walking out of the car at the beginning. His refusal to go with the people that knocked on his door until his saw the white rabbit. The Oracle telling him that she'd ask him to sit down, but that he isn't going to anyways. The "No, you're other left" scene. His refusal to listen to Tank telling him that they have to pull the plug on Morpheus. Did the Oracle know about this? Almost certainly.
Some may think that I'm reading too much into this. Perhaps I am. But pieces fit so clearly that I'm incredulous to think that it was mere chance that this message was put into the movie. Messages about fighting on and surviving and control, sure. But the way it was pieced together is no coincidence. Even the spoon bending. It was a metaphor for predicting the future. There is no spoon. Some say this means that the spoon doesn't actually exist because it's in the Matrix. In some ways, this is true. But what it's really about is that everything in the Matrix is a reflection of yourself. It's also a commentary on the Oracle. That things won't happen unless YOU make the decision. No one else will make the decision for you.
She told you exactly what you needed to hear, that's all.
This is probably my favourite line. It debunks what most people think the Halting Problem is about. When you take into account the above quote, it all falls apart. Everything ends up being about what you do with the information you are given. Is it true? Is it false? Does that affect either way if others can determine your actions?