HOUSE_OVERSIGHT_015966.jpg

276
Are the Androids Dreaming Yet?

assumes each could be correct and travels down both. Solving a problem using a machine like this can be fast. The problem is this machine has no greater power than a regular Turing machine. Let me show you why.

A non-deterministic machine is essentially the same as a single Turing machine; each time there is a branch in the program you would start running two processes. The first process works on every even tick of the computer clock and the other on every odd tick. Now we have a single machine running two branches at the same time. Using this trick over and over again, a single machine can run a program exploring every possible branch. Although it generates an enormous number of branches and takes a huge time to run, it is still a single machine and we have an infinity of time on our hands. Therefore, the machine is limited as before.

We are not doing well so far and we have already exhausted an infinite number of options! Let’s try a different tack. We know true randomness is non-computable, the sort of randomness generated by the Lavarand we examined earlier in the book. Might this help? Truly random processes can’t be simulated by a computer. If we throw this into the pot might it let us compute something a Turing machine cannot?

Again, no.

This idea still only generates a machine as powerful as the non-deterministic machine above. A non-deterministic Turing machine runs every possible program. All a random one does is choose some of the same paths at random. It, therefore, can’t be any more powerful. The one difference is that it can generate non-computable numbers. However, the only interesting characteristic of these numbers is they are truly random and this randomness was an input. Their presence does not make the machine any more powerful.

There are quite a few proposals for hyper-computers that are just cleverly dressed up versions of the machines we have already met and dismissed. For example, it has been proposed the Internet could form a super-Turing machine. This is known as a site machine because the processing is distributed across many sites linked together through the Internet. It is proposed each site could act as an oracle to the others. This is quite an elegant idea, and some proofs have been offered that show such a machine is capable of generating non-computable functions. The problem with this idea is that you can simply draw an imaginary line around the whole site machine and it looks exactly like a big Turing machine. There is no conceptual difference between such a machine and a regular computer with subroutines. After all, that’s in Turing’s

HOUSE_OVERSIGHT_015966