So what does it mean to say that we can build a machine to solve non-Turing-computable problems? David Deutsch, who is a quantum physicist working at the Maths Institute in Oxford, has argued that computability lecture) is not a purely mathematical notion, but is an abstraction from physics. He says that the Turing machine is an abstract description of those basic operations that, because of the nature of our universe, we find easy to perform. In other universes, with other laws of physics, what's computable might be quite different.

According to Deutsch, many mathematicians and computer scientists regard
computability as a mathematical property of numbers, functions, etc in
the same way that (say) oddness and evenness are. But it isn't. It's
just an abstraction from our physical experience. It is logically
possible that there could be physical systems which could perform
computations beyond the power of any Turing machine (and hence, of any
digital computer). I'll use the phrase *Turing-equivalent computer*
again to denote anything that has the same computational power as a
Turing machine, i.e. any digital computer.

For example, let's suppose we have some scheme for arrangine all the
possible computer programs in some language such that each is indexed by
a unique integer. So `begin end`

gets 1, `begin stop end`

gets
2, `begin a:=1 end`

gets 3, and so on. Now imagine that we have
found a strange crystal which is perfectly opaque to some wavelengths of
electromagnetic radiation, perfectly transparent to others, and explodes
with yet others. On further investigation, it turns out that is opaque
to exactly those wavelengths of radiation whose length in metres is the
index of a program that will halt. It's transparent to exactly those
wavelengths of radiation whose length in metres is the index of a
program that will never halt. If illuminated with any other wavelength,
it explodes.

In our universe, this is (as far as we know!) impossible. But it's an impossibility dictated by the laws of physics, not those of logic. In other universes, perhaps such a ``halting crystal'' could exist.

But is it possible for matter that goes beyond computability to exist in
*our* universe? If it is, then that's important to AI. The brain
could be made of such matter, and hence have computational powers that
go beyond any Turing-equivalent computer.

Penrose believes such matter can exist, and that the brain is composed
of it. Deutsch believes such matter can exist, but that the brain is not
composed of it. However, says Deutsch, we may be able to build *computers* composed of it. So in Deutsch's view, the computer might
eventually outdo the brain. In Penrose's view, the brain outdoes the
computer. See *Emperor's New Mind* page 146.

Let me now describe each case.

Wed Feb 14 23:51:11 GMT 1996