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
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,
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.