Matter that can compute the uncomputable

Next: Deutsch - computers may use matter that outdoes the
Up: Penrose
Previous: Penrose
Back: to main list of student notes

## Matter that can compute the uncomputable

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.

Next: Deutsch - computers may use matter that outdoes the
Up: Penrose
Previous: Penrose
Back: to main list of student notes

Jocelyn Ireson-Paine
Wed Feb 14 23:51:11 GMT 1996