The Fabric of Reality David Deutch

6 
Universality and the Limits of Computation
 
The heart of a virtual-reality generator is its computer, and the question of
what environments can be rendered in virtual reality must eventually come
down to the question of what computations can be performed. Even today,
the repertoire of virtual-reality generators is limited as much by their
computers as by their image generators. Whenever a new, faster computer,
with more memory and better image-processing hardware, is incorporated
into a virtual-reality generator, the repertoire is enlarged. But will this always
be so, or will we eventually encounter full universality, as I have argued we
should expect to in the case of image generators? In other words, is there a
single virtual-reality generator, buildable once and for all, that could be
programmed to render any environment that the human mind is capable of
experiencing?
Just as with image generators, we do not mean by this that it single virtual-
reality generator might contain within itself the specifications of all logically
possible environments. We mean only that for every logically possible
environment it would be possible lo program the generator to render that
environment. We can envisage encoding the programs on, for example,
magnetic disks. The more complex the environment, the more disks may be
needed in store the corresponding program. So to render complex
environments the machine must have a mechanism, just as I have described
for the universal image generator, that can read unlimited numbers of disks.
Unlike an image generator, a virtual-reality generator may need a growing
amount of ‘working memory’ to store the intermediate results of its
calculations. We may envisage this as being provided in the form of blank
disks. Once again, the fact that a machine needs to be supplied with energy,
blank disks and maintenance does not prevent us from regarding it as a
‘single machine’, provided that these operations are not tantamount to
changing the machine’s design, and are not forbidden by the laws of
physics.
In this sense, then, a computer with an effectively unlimited memory capacity
can be envisaged in principle. But a computer with an unlimited speed of
computation cannot. A computer of given design will always have a fixed
maximum speed, which only design changes can increase. Therefore a
given virtual-reality generator will not be able to perform unlimited amounts
of computation per unit time. Will this not limit its repertoire? If an
environment is so complex that the computation of what the user should be
seeing one second from now takes the machine more than one second to
compute, how can the machine possibly render that environment accurately?
To achieve universality, we need a further technological trick.
To extend its repertoire as far as is physically possible, a virtual-reality
generator would have to take control of one further attribute of the user’s
sensory system, namely the processing speed of the user’s brain. If the
human brain were like an electronic computer, this would simply be a matter
of changing the rate at which its ‘clock’ emits synchronizing pulses. No doubt
the brain’s ‘clock’ will not be so easily controlled. But again this presents no
problem of principle. The brain is a finite physical object, and all its functions
are physical processes which in principle can be slowed down or stopped.

---

The ultimate virtual-reality generator would have to be capable of doing that.
To achieve a perfect rendering of environments which call for a lot of
computation, a virtual-reality generator would have to operate in something
like the following way. Each sensory nerve is physically capable of relaying
signals at a certain maximum rate, because a nerve cell which has fired
cannot fire again until about one millisecond later. Therefore, immediately
after a particular nerve has fired, the computer has at least one millisecond
to decide whether, and when, that nerve should fire again. If it has computed
that decision within, say, half a millisecond, no tampering with the brain’s
speed is necessary, and the computer merely fires the nerve at the
appropriate times. Otherwise, the computer causes the brain slow down (or,
if necessary, to stop) until the calculation of what should happen next is
complete; it then restores the brain’s normal speed. What would this feel like
to the user? By definition, like nothing. The user would experience only the
environment specified in the program, without any slowing down, stopping or
restarting. Fortunately it is never necessary for a virtual-reality generator to
make the brain operate 
faster than normal; that would eventually raise
problems of principle because, among other things, no signal can travel
faster than the speed of light.
This method allows us to specify in advance an arbitrarily complicated
environment whose simulation requires any finite amount of computation,
and to experience that environment at any subjective speed and level of
detail that our minds are capable of assimilating. If the requisite calculations
are too numerous for the computer to perform within the subjectively
perceived time, the experience will be unaffected, but the user will pay for its
complexity in terms of externally elapsed time. The user might emerge from
the virtual-reality generator after what seemed subjectively like a five-minute
experience, to find that years had passed in physical reality.
A user whose brain is switched off, for however long, and then switched on
again will have an uninterrupted experience of some environment. But a
user whose brain is switched off for ever has no experiences at all from that
moment on. This means that a program which might at some point switch
the user’s brain off, and never switch it on again, does not generate an
environment for the user to experience and therefore does not qualify as a
valid program for a virtual-reality generator. But a program which, eventually,
always switches the user’s brain back on causes the virtual-reality generator
to render some environment. Even a program which emits no nerve signals
at all renders the dark, silent environment of perfect sensory isolation.
In our search for the ultimate in virtual-reality we have strayed a very long
way from what is feasible today, or even from what is on any foreseeable
technological horizon. So let me stress again that for our present purposes
technological obstacles are irrelevant. We are not investigating what sorts of
virtual-reality generator can be built, or even, necessarily, what sorts of
virtual-reality generator will ever be built, by human engineers. We are
investigating what the laws of physics do and do not allow in the way of
virtual reality. The reason why this is important has nothing to do with the
prospects for making better virtual-reality generators. It is that the relation
ship between virtual reality and ‘ordinary’ reality is part of the deep,
unexpected structure of the world, which this book is about.

---

By considering various tricks — nerve stimulation, stopping and starting the
brain, and so on — we have managed to envisage a physically possible
virtual-reality generator whose repertoire covers the entire sensory range, is
fully interactive, and is not constrained by the speed or memory capacity of
its computer. Is there anything outside the repertoire of such a virtual-reality
generator? Would its repertoire be the set of all logically possible
environments? It would not. Even this futuristic machine’s repertoire is
drastically circumscribed by the mere fact of its being a physical object. It
does not even scratch the surface of what is logically possible, as I shall now
show.
The basic idea of the proof — known as a 
diagonal argument — predates
the idea of virtual reality. It was first used by the nineteenth-century
mathematician Georg Cantor to prove that there are infinite quantities
greater than the infinity of natural number (1, 2, 3…). The same form of proof
is at the heart of the modern theory of computation developed by Alan
Turing and others in the 1930s. It was also used by Kurt Gödel to prove his
celebrated ‘incompleteness theorem’, of which more in Chapter 10.
Each environment in our machine’s repertoire is generated by some program
for its computer. Imagine the set of all valid programs for this computer.
From a physical point of view, each such program specifies a particular set
of values for physical variables, on the disks or other media, that represent
the computer’s program. We know from quantum theory that all such
variables are quantized, and therefore that, no matter how the computer
works, the set of possible programs is discrete. Each program can therefore
be expressed as a finite sequence of symbols in a discrete code or computer
language. There are infinitely many such programs, but each one can
contain only a finite number of symbols. That is because symbols are
physical objects, made of matter in recognizable configurations, and one
could not manufacture an infinite number of them. As I shall explain in
Chapter 10, these intuitively obvious physical requirements — that the
programs must be quantized, and that each of them must consist of a finite
number of symbols and can be executed in a sequence of steps — are more
substantive than they seem. They are the only consequences of the laws of
physics that are needed as input for the proof, but they are enough to
impose drastic restrictions on the repertoire of any physically possible
machine. Other physical laws may impose even more restrictions, but they
would not affect the conclusions of this chapter.
Now let us imagine this infinite set of possible programs arranged in an
infinitely long list, and numbered Program 1, Program 2, and on. They could,
for instance, be arranged in ‘alphabetical’ order with respect to the symbols
in which they are expressed. Because each program generates an
environment, this list can also be regarded as a list of all the environments in
the machine’s repertoire; we may call them Environment 1, Environment 2,
and so on. It could be that some of the environments are repeated in the list,
because two different programs might in effect perform the same
calculations, but that will not affect the argument. What is important is that
each environment in our machine’s repertoire should appear at least once in
the list.
A simulated environment may be limited or unlimited in apparent physical
size and apparent duration. An architect’s simulation of a house, for

---

example, can be run for an unlimited time, but will probably cover only a
limited volume. A video game might allow the user only a finite time for play
before the game ends, or it might render a game-universe of unlimited size,
allow an unlimited amount of exploration and end only when the user
deliberately ends it. To make the proof simpler, let us consider only
programs that continue to run for ever. That is not much of a restriction,
because if a program halts we can always choose to regard its lack of
response as being the response of a sensory-isolation environment.
Let me define a class of logically possible environments which I shall call
Cantgotu environments, partly in honour of Cantor, Gödel and Turing, and