HOUSE_OVERSIGHT_015968.jpg

278
Are the Androids Dreaming Yet?

calculation can be the limiting factor. A quantum computer is very space
efficient. When the computer branches and makes a copy of itself, it does
so without needing more space. There are two theories for how it does
this, (well, three, but the third is highly controversial). The first theory is
the computer doesn't need the space because it hasn't made its mind up
yet; somehow the calculation floats in an undecided state. The second is
that the computer puts a copy of itself in a parallel Universe each time it
branches. When the calculation is over, either all the Universes collapse
to a decision, or every possibility is chosen in some Universe or other and
they all go on their merry way! This is the ‘many-worlds’ interpretation
of quantum mechanics and we will return to it later in the book.

We have now explored all the straightforward ways to make a hyper-
computer, and all have failed. We need something still more exotic.

More Horse Power Needed
Is there anything more powerful than a Turing machine?
Yes, in theory, there is.
The first person to explore ways of breaking the Turing limit was
Turing himself. He cut right through the problem by proposing the
existence of an oracle function. At any point in a computation, you could
ask this function a question and it would give you the right answer.
We must leave completely aside the question of how this wonderful
oracle function is constructed. All we know is it can't be a machine. If it
really existed, a Turing machine that was able to consult it would be able
to answering any question you put to it. That is a hyper-computer.
Unfortunately having access to such an oracle does not get us far.
We can use it to compute numbers we could not otherwise have obtained
– or answer a single question – but it does not give us a general-purpose
way to solve further problems outside of the logical area we asked it to
answer.
Each time the oracle answers a question we break the limit a tiny
bit. Each question and each answer moves us forward, but does not give
us something universally applicable. If I ask the oracle to prove Fermat’s
Last Theorem it will give me that answer, but this does not turn me into
a creative mathematician, able to prove any other theory. You can test
this by typing a mathematical question into the Google search box. Does
obtaining an answer make you better at mathematics?
In any case, an oracle is not and cannot be a machine, so it does not
lead us any further in our quest to build something super-Turing.

HOUSE_OVERSIGHT_015968