David Deutch - The Fabric of Reality

Thus our hypothetical project of building the ultimate virtual-reality generator, which had been going so well, has suddenly run into a brick wall. Whatever improvements may be made in the distant future, the repertoire of the entire technology of virtual reality will never grow beyond a certain fixed set of environments. Admittedly this set is infinitely large, and very diverse by comparison with human experience prior to virtual-reality technology. Nevertheless, it is only an infinitesimal fraction of the set of all logically possible environments.

What would it feel like to be in a Cantgotu environment? Although the laws of physics do not permit us to be in one, it is still logically possible and so it is legitimate to ask what it would feel like. Certainly, it could give us no new sensations, because a universal image generator is possible and is assumed to be part of our high-technology virtual-reality generator. So a Cantgotu environment would seem mysterious to us only after we had experienced it and reflected on the results. It would go something like this. Suppose you are a virtual-reality buff in the distant, ultra-high-techhnology future. You have become jaded, for it seems to you that you have already tried everything interesting. But then one day a genie appears and claims to be able to transport you to a Cantgotu environment. You are sceptical, but agree to put its claim to the test. You are whisked away to the environment. After a few expedients you seem to recognize it — it responds just like one of your favourite environments, which on your home virtual-reality system has program number X. However, you keep experimenting, and eventually, during the Xth subjective minute of the experience, the environment responds in a way that is markedly different from anything that Environment X would do. So you give up the idea that this is Environment X. You may then notice that everything that has happened so far is also consistent with another renderable environment, Environment Y. But then, during the Yth subjective minute you are proved wrong again. The characteristic of a Cantgotu environment is simply this: no matter how often you guess, no matter how complex a program you contemplate as being the one that might be rendering the environment, you will always be proved wrong because no program will render it, on your virtual reality generator or on any other.

Sooner or later you will have to bring the test to a close. At that point you may well decide to concede the genie’s claim. That is nor to say that you could ever prove that you had been in a Cantgotu environment, for there is always an even more complex program that the genie might have been running, which would match your experiences so far. That is just the general feature of virtual reality that I have already discussed, namely that experience cannot prove that one is in a given environment, be it the Centre Court at Wimbledon or an environment of the Cantgotu type.

Anyway, there are no such genies, and no such environments. So we must conclude that physics does not allow the repertoire of a virtual-reality generator to be anywhere near as large as logic alone would allow. How large can it be?

Since we cannot hope to render all logically possible environments, let us consider a weaker (but ultimately more interesting) sort of universality. Let us define a universal virtual-reality generator as one whose repertoire contains that of every other physically possible virtual-reality generator. Can such a machine exist? It can. Thinking about futuristic devices based on computer-controlled nerve stimulation makes this obvious — in fact, almost too obvious. Such a machine could be programmed to have the characteristics of any rival machine. It could calculate how that machine would respond, under any given program, to any behaviour by the user, and so could render those responses with perfect accuracy (from the point of view of any given user). I say that this is ‘almost too obvious’ because it contains an important assumption about what the proposed device, and more specifically its computer, could be programmed to do: given the appropriate program, and enough time and storage media, it could calculate the output of any computation performed by any other computer, including the one in the rival virtual-reality generator. Thus the feasibility of a universal virtual-reality generator depends on the existence of a universal computer — a single machine that can calculate anything that can be calculated.

As I have said, this sort of universality was first studied not by physicists but by mathematicians. They were trying to make precise the intuitive notion of ‘computing’ (or ‘calculating’ or ‘proving’) something in mathematics. They did not take on board the fact that mathematical calculation is a physical process (in particular, as I have explained, it is a virtual-reality rendering process), so it is impossible to determine by mathematical reasoning what can or cannot be calculated mathematically. That depends entirely on the laws of physics. But instead of trying to deduce their results from physical laws, mathematicians postulated abstract models of ‘computation’, and defined ‘calculation’ and ‘proof’ in terms of those models. (I shall discuss this interesting mistake in Chapter 10.) That is how it came about that over a period of a few months in 1936, three mathematicians, Emil Post, Alonzo Church and, most importantly, Alan Turing, independently created the first abstract designs for universal computers. Each of them conjectured that his model of ‘computation’ did indeed correctly formalize the traditional, intuitive notion of mathematical ‘computation’. Consequently, each of them also conjectured that his model was equivalent to (had the same repertoire as) any other reasonable formalization of the same intuition. This is now known as the Church-Turing conjecture.

Turing’s model of computation, and his conception of the nature of the problem he was solving, was the closest to being physical. His abstract computer, the Turing machine, was abstracted from the idea of a paper tape divided into squares, with one of a finite number of easily distinguishable symbols written on each square. Computation was performed by examining one square at a time moving the tape backwards or forwards, and erasing or writing one of the symbols according to simple, unambiguous rules. Turing proved that one particular computer of this type, the universal Turing machine, had the combined repertoire of all other Turing machines. He conjectured that this repertoire consisted precisely of ‘every function that would naturally be regarded as computable’. He meant computable by mathematicians.

But mathematicians are rather untypical physical objects. Why should we assume that rendering them in the act of performing calculations is the ultimate in computational tasks? It turns out that it is not. As I shall explain in Chapter 9, quantum computers can perform computations of which no (human) mathematician will ever, even in principle, be capable. It is implicit in Turing’s work that he expected what ‘would naturally be regarded as computable’ to be also what could, at least in principle, be computed in nature. This expectation is tantamount to a stronger, physical version of the Church-Turing conjecture. The mathematician Roger Penrose has suggested that it should be called the Turing principle:

(for abstract computers simulating physical objects)

There exists an abstract universal computer whose repertoire includes any computation that any physically possible object can perform.

Turing believed that the ‘universal computer’ in question was the universal Turing machine. To take account of the wider repertoire of quantum computers, I have stated the principle in a form that does not specify which particular ‘abstract computer’ does the job. The proof I have given of the existence of Cantgotu environments is essentially due to Turing. As I said, he was not thinking explicitly in terms of virtual reality, but an ‘environment that can be rendered’ does correspond to a class of mathematical questions whose answers can be calculated. Those questions are computable. The remainder, the questions for which there is no way of calculating the answer, are called non-computable. If a question is non-computable that does not mean that it has no answer, or that its answer is in any sense ill-defined or ambiguous. On the contrary, it means that it definitely has an answer. It is just that physically there is no way, even in principle, of obtaining that answer (or more precisely, since one could always make a lucky, unverifiable guess, of proving that it is the answer). For example, a prime pair is a pair of prime numbers whose difference is 2, such as 3 and 5, or 11 and 13. Mathematicians have tried in vain to answer the question whether there are infinitely many such pairs, or only a finite number of them. It is not even known whether this question is computable. Let us suppose that it is not. That is to say that no one, and no computer, can ever produce a proof either that there are only finitely many prime pairs or that there are infinitely many. Even so, the question does have an answer: one can say with certainty that either there is a highest prime pair or there are infinitely many prime pairs; there is no third possibility. The question remains well-defined, even though we may never know the answer.