The Fabric of Reality David Deutch

partly for a reason I shall explain shortly. They are defined as follows. For
the first subjective minute, a Cantgotu environment behaves differently from
Environment 1 (generated by Program 1 of our generator). It does not matter
how it does behave, so long as it is, to the user, recognizably different from
Environment 1. During the second minute it behaves differently from
Environment 2 (though it is now allowed to resemble Environment 1 again).
During the third minute, it behaves differently from Environment 3, and so
on. Any environment that satisfied these rules I shall call a Cantgotu
environment.
Now, since a Cantgotu environment does not behave exactly like
Environment 1, it cannot 
be Environment 1; since it does not behave exactly
like Environment 2, it cannot 
be Environment 2. Since it is guaranteed
sooner or later to behave differently from Environment 3, Environment 4 and
every other environment on the list, it cannot be any of those either. But that
list contains all the environments that are generated by every possible
program for this machine. It follows that none of the Cantgotu environments
are in the machine’s repertoire. The Cantgotu environments are
environments that we 
can’t go to using this virtual-reality generator.
Clearly there are enormously many Cantgotu environments, because the
definition leaves enormous freedom in choosing how they should behave,
the only constraint being that during each minute they should not behave in
one particular way. It can be proved that, for every environment in the
repertoire of a given virtual-reality generator, there are infinitely many
Cantgotu environments that it cannot render. Nor is there much scope for
extending the repertoire by using a range of different virtual-reality
generators. Suppose that we had a hundred of them, each (for the sake of
argument) with a different repertoire. Then the whole collection, combined
with the programmable control system that determines which of them shall
be used to run a given program, is just a larger virtual-reality generator. That
generator is subject to the argument I have given, so for every environment
it can render there will be infinitely many that it cannot. Furthermore, the
assumption that different virtual-reality generators might have different
repertoires turns out to be over-optimistic. As we shall see in a moment, all
sufficiently sophisticated virtual-reality generators have essentially the same
repertoire.
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:

---

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