Stochastic and Quantum Computation

When noise is added to the McCullough-Pitts network, it is no longer a Turing machine. It is a
stochastic computer — a computer which involves chance as well as the precise following of
instructions. The error-ridden neural network is merely one type of stochastic computer. Every
real computer is a stochastic computer, in the sense that it is subject to random errors. In some situations, randomness is a nuisance; one hopes it will not interfere too much with computation.

But in other situations, chance may be an essential part of computation. Many Turing machine
algorithms, such as Monte Carlo methods in numerical analysis, use various mathematical ruses
to simulate stochasticity.

As I will argue later, one may view randomness in the neural network as a blessing in disguise.
After all, one might well wonder: if the brain is a computer, then where do new ideas come
from? A deterministic function only rearranges its input. Is it not possible that innovation
involves an element of chance?

One may define a stochastic Turing machine as a computer identical to a Turing machine
except that its program may contain references to chance. Forinstance, its processing unit might
contain commands like:

If the tape reads D and -A+(B-C)(D+E)=(R-J), then move tape to the left with probability 50% and move it to the right with probability 50%, call what is read C, move the tape two to the right, write (D-B)Con the tape with probability 25% and write C on the tape with probability 75%.

One may construct a theory of stochastic Turing machines parallel to the ordinary theory of
computation. We have seen that a universal Turing machine can follow any precise set of
instructions, at least in the sense that it can simulate any other computer. Similarly, it can be shown that there is a universal stochastic Turing machine which can simulate any precise set of instructions involving chance operations.

QUANTUM COMPUTATION
If the universe were fundamentally deterministic, the theory of stochastic computation would
be superfluous, because there could never really be a stochastic computer, and any apparent
randomness we perceived would be a consequence of deterministic dynamics. But it seems that
the universe is not in fact deterministic. Quantum physics tells us that chance plays a major role in the evolution of the physical world. This leads us to the question: what kind of computer can simulate any physical system? What kind of computer can follow any precise set of physical instructions?

It turns out that neither a Turing machine nor a stochastic Turing machine has this property.
This puts the theory of computation in a very uncomfortable situation. After all, the human brain is a physical system, and if computers cannot simulate any physical system, there is no reason to simply assume that they can simulate the human brain. Perhaps they can, but there is no reason to believe it. Clearly it would be desirable to design a computer which could simulate an arbitrary physical system. Then we would have a much better claim to be talking about computation in general.

As mentioned above, D. Deutsch (1985) has taken a large step toward providing such a
computer. He has described the quantum Turing machine, which according to the laws of
quantum physics can simulate the behavior of any finite physical system within an arbitrarily
small degree of error. It can simulate any Turing machine, and any stochastic Turing machine,
with perfect accuracy. Of course, the rules of quantum physics may be revised any day now;
there are a number of pressing problems. But Deutsch’s idea is a major advance.

There is much more to be said on the topic of quantum computation. But for now, let us
merely observe that the question "what is a computer?" is hardly resolved. It may never be.
Various abstract models may shed light on differentissues, but they are never final answers. In
the last analysis, "precise instructions" is just as elusive a concept as "intelligence" or "mind."

belgesi-931

Belgeci