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.
In virtual-reality terms: no physically possible virtual-reality generator can render an environment in which answers to non-computable questions are provided to the user on demand. Such environments are of the Cantgotu type. And conversely, every Cantgotu environment corresponds to a class of mathematical questions (‘what would happen next in an environment defined in such-and-such a way?’) which it is physically impossible to answer.