Halting prophecy
Oracle of Delphi doesn’t exist for the same reason you can’t solve the halting problem
Context
Halting problem is the problem of writing a computer program that could take the code of another program and decide if it will finish its execution or run forever when run on a particular input. The idea is that you might have a large piece of software and you’d like to check whether everything works properly or whether there is a possibility for the program to get stuck in an infinite loop.
The problem can’t be solved – there is no such program. The problem is a part of the lore of computer science because the argument for why it can’t be solved appeared in one of Alan Turing’s first papers on the subject and the technique used for demonstrating this impossibility is at the heart of many similar results.
That writing such a program is difficult is revealed quickly the moment you stop associating “code of another program” with a useful piece of software a software engineer might write. The space of computer programs is much bigger and incredibly rich. It presumably contains some sort of AIs, detailed simulations involving technology that hasn’t been invented yet and much more. Computation, after all, has the capacity to be about anything. Many intuitions and expectations we have about this space, due to the software we currently write, do not hold for most of it.
To see just a small part of the challenge the solution to the halting problem would need to overcome consider programs whose ultimate behavior depends on the truth of difficult, perhaps still unproven, mathematical conjectures. Take for example Fermat’s last theorem. It asks whether there is an integer solution to
for some n greater than 3. You can write a computer program that systematically tries all possible values of n, x, y and z and halts if it finds a solution that works. If Fermat’s last theorem is true the program will run forever, otherwise it will stop. So definitively figuring out whether that program gets stuck in an infinite loop fruitlessly trying ever bigger numbers or whether it eventually exits it is as hard as proving the conjecture.
But difficult is not the same as impossible and hence the question remains – is there a nice way of seeing why the existence of such a program should not be possible even in principle?
It turns out you can find the answer in a well-known ancient Greek legend – the Oedipus myth. The myth begins with the oracle of Delphi prophesying to the king that his son will murder him and marry his wife. The rest of the story then revolves around attempts by various people to avert the prophecy while inadvertently and unknowingly bringing it about.
What is the connection? It turns out that trying to predict a newborn’s future and prophesying whether a program will halt have something in common.
The problem with prophecy
There are many conceptual issues that have been identified around prediction and prophecy. Be it Newcomb’s paradox or the idea that it’s impossible to prophesy knowledge we don’t yet have, there seem to be some purely conceptual limitations on our ability to know things about the future in the present. Most of these ultimately revolve around the fact that we don’t exist outside the future we’re trying to predict but are a part of it. To be able to fully control or predict something, to fully objectify it in a sense, seems to require us to fully contain it and exist outside of it. And nobody can do this with the entire world they are themselves a part of.
Oedipus myth points to one such specific difficulty with prophecy – if we are told that we will do something in the future, why can’t we just choose to do otherwise? Indeed, why can’t us being told we will do something, be the very reason we choose to do otherwise?
The myth gets around this difficulty by essentially painting characters as powerless and unable to understand the consequences of their actions. They think they are averting the prophecy, but instead they are bringing it about through a series of outlandish events.
But one must wonder just how far this imbalance between the oracle’s predictive omniscience and everybody else’s predictive failure can be pushed. Imagine you visit the Oracle and on the way in notice there is a nice ice-cream booth right outside the temple. Rather than asking the Oracle about how your life will play out, you ask her which flavour of ice-cream you will get on the way out. If the oracle predicts you will get a chocolate, can’t you just get vanilla? And if she says you’ll get vanilla, why can’t you just get chocolate?
A sufficiently magical oracle with inexplicable powers could presumably get out of this as well. But in the context of the halting problem, we are only dealing with computer programs which have some limitations.
To see the analogy between the two situations: a hypothetical program that could determine whether all others halt is a kind of an oracle, prophesying every other program’s ultimate fate. Could any of them somehow learn its predictions and act against them? It seems like the answer to that might be no since every piece of software is at least for these purposes assumed to be self-contained, not interacting with anything other than their input or output devices.
But this oracular program is itself just a program – a piece of code – and it is therefore entirely possible for other programs to have a copy of it embedded within themselves and use it as a subroutine. If this program is now presented with an input all it needs to do to learn the prediction about its own behaviour is to ask the oracle subroutine what it will do, by feeding it its own code and the input. If the oracle says it will halt it enters an infinite loop, if it says it will run forever it halts. It thereby refutes its prophecy showing the subroutine isn’t really an omniscient oracle after all.
There are a few loose technical details here such as for example – where does this program get its own code to prompt the oracle with? There are several ways out of this: one of them is that rather than prompting the oracle with its own code and input x, it instead places the input x in place of its own code as well. When this program then gets its own code on the input, the situation becomes analogous as before, once again demonstrating oracle’s failure of prophecy on at least one input.
So this is why you can’t solve the halting problem – for every program that makes predictions about the ultimate behavior of other programs, there are others that contain it as a subroutine, use it to make predictions about their own behavior and then act against them.
There is nothing special about halting
While the halting problem has become the most well-known example of such an unsolvable problem (they are often called undecidable) what this explanation allows us to see is that there is in some sense nothing fundamental about it. Any problem that involves some sort of prophesizing about the ultimate behavior of a computer program is undecidable for the very same reason. This includes things other than halting. Does the program solve the shortest path problem? Will it ever enter some loop in its code when run on this input?
All undecidable in their general form for the same reason. All questions of the form “does this program do X” can’t have a general procedure that gives the correct answer for all programs. They are all vulnerable to the move of seeing whether we’re predicted to do X – and then doing the opposite.
There is a theorem called Rice’s theorem which captures this idea. While the proof you can see on the Wikipedia page reduces all such problems to the halting problem, really any of them would work as a starting point. In a different universe a different Turing could have easily picked some other such question and it could easily become the quintessential undecidable problem. It is all ultimately about prophecy.
What, if anything, does this say about prediction and prophecy in real life?
So this explains the connection between the halting problem and prophecy. But does this rather abstract argument really tell us anything about prediction and prophecy in the real world? People are constantly thinking about the future, about what other people will do and in certain contexts where the whole of society and civilization is going. Understanding the limits and possibility when it comes to that remains surrounded by ambiguity. What can we learn from this argument?
The argument seems to point to the fact that our ability to definitively predict the future seems to be related with our inability or unwillingness to affect it. It is very interesting to explore what predictions about the future have that property. Perhaps the predicted future is so awesome nobody will want to do anything but help bring it about. Perhaps it is so mundane nobody will care to do anything other than to let it happen. Do most predictions have either of these properties?
But perhaps more importantly, the argument points to interesting facts about the the role self-knowledge plays as a source of novelty and unpredictability in the world.
It is often thought the world seems unpredictable to us because we lack a complete understanding of it. And so the expectation is that if we improved our understanding of the world, it would become more predictable to us. But what this argument highlights is this is not quite true.
There is a well-known Douglas Adams quote: “There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable”.
There is a very real sense in which this is literally true of us. There are things we currently don’t understand about ourselves, about what we do and why we do it. Presumably we will in the future and in light of that understanding the events happening right now will not be given the same meaning then as they are given now. But the moment we’ll reach that understanding something surprising will happen.
Rather than this understanding finally allowing us to predict the future, it will instead be something that pushes us into the unknown, for it will allow us to move beyond our established patterns and ways of doing things. Our not understanding ourselves as we are now is an essential part of us as we are now – and once we reach that understanding we become something new. It is recognising our ways that allows us to act differently.
The quest for self-understanding and self-transcendence are then in some sense one and the same thing. Our increasing understanding of the world makes us less, not more predictable. We are constantly diagonalizing against ourselves.
And perhaps one final note. Many people believe predictions other people make about their future. It stands to reason that many people are held back by believing such predictions. If you believe predictions others have for you, remember the supernatural oracle. They are not that. But how far away from that are they? What kinds of knowledge might allow one to confidently predict another’s future? How might it be acquired? Just what kind of an oracle are they?
Could they predict what ice-cream you will get on the way out?
Thanks to Hana Skitek, Charles Bédard and Jake Orthwein for comments on earlier drafts.