Say we had some way of automagically deciding the truth or falsity of some undecidable problem, like, say, the halting problem. Would it then be possible to compute everything? Well, the answer is, oddly enough, not quite. To explore the ramifications of this problem, which leads into the murky world of hypercomputation, Alan Turing proposed in the 1938 paper "Systems of Logic Based on Ordinals" the idea of an oracle Turing machine.

Say, we have some formal language A, which may possibly be not recursively enumerable. A Turing machine with an oracle on A is simply a single-tape TM with three special states, labeled q?, qy, and qn. If the TM enters the state q?, it goes to qy if the string of tape symbols on the left of the tape head is in the language A or qn otherwise. In other words, the state q? consults the oracle, which then tells the machine whether the contents of the tape satisfy the language it is an oracle of. Obviously, if the language A is recursively enumerable, then the oracle may be simulated by another Turing machine, and the O-machine (as Turing called them) has no greater computing power than an ordinary TM. But if the language A is not recursive, then the O-machine may be capable of accepting languages which are not recursively enumerable. We denote such an O-machine with an oracle A as MA.

So to return to the original question, if we had an oracle for the halting problem or some other undecidable question, would everything then magically become decidable as well? Well, the short, and somewhat surprising answer is no. One of the first things we notice is that such O-machines are in many ways the same as ordinary Turing machines; you can still build a universal Turing machine with an oracle capable of simulating any other TM with the same oracle, and hence, you still have description numbers for any such O-machine. The addition of an oracle did not change the fact that the set of all of your O-machines remains denumerable, while the class of all formal languages is non-denumerable, so there must always still exist some set of languages that your O-machines cannot accept.

Further, it may be shown that some undecidable problems are actually "harder" than others. If we had such an oracle for the halting problem, then the set of all O-machines with that oracle has a halting problem of its own. Even these O-machines cannot solve their own halting problem! And if we had another oracle for that halting problem, the set of O-machines with both oracles would still have its own halting problem and so on, producing an infinite hierarchy of undecidable sets, each set "more undecidable" than the last. This kind of hierarchy is called the Kleene-Mostowski Arithmetical Hierarchy.

One example of a problem that is provably harder than the halting problem in this sense is the question of whether or not for some Turing machine M with an alphabet Σ, L(M) = Σ*. It may be shown that even an O-machine MH endowed with an oracle for the halting problem H cannot decide that particular problem. You'd need the oracle for the halting problem for those O-machines as well to decide that particular problem.

As a side note, I cannot help but think that the Wachowski Brothers were actually reading much of Turing's bibliography while they developed the scripts for The Matrix trilogy. It would appear that they conceived of the Matrix as something of a Turing machine, with the Architect as the personification of the ultimate universal Turing machine. The Oracle is an oracle of exactly the type described here, in that she directs the evolution of the Matrix by giving humans like Neo choices whose consequences cannot be foreseen, and are in a sense non-deterministic, and thus attempting to tap into whatever formal language is represented by humans. The exploration of the relationship between the philosophy of the Matrix and these questions at the foundations of mathematics is the topic for another node...


Hopcroft, John E. and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation

Homer, Steven and Alan L. Selman, Computability and Complexity Theory.

Ord, Toby, "Hypercomputation: computing more than the Turing machine"

Turing, A.M., "On computable numbers, with an application to the Entscheidungsproblem"

Turing, A.M., "Systems of Logic Based on Ordinals"