This post is part of my attempt to understand the discussion of Godel’s incompleteness theorem presented in The Fabric of Reality by David Deutsch (DD).
See part 2 here
In Chapter 10 of The Fabric of Reality, DD says:
Godel proved that if a set of rules of inference in some (sufficiently rich) branch of mathematics is consistent (whether provably so or not), then within that branch of mathematics there must exist valid methods of proof that those rules fail to designate as valid. This is called Godel’s incompleteness theorem. To prove his theorems, Godel used a remarkable extension of the Cantor ‘diagonal argument’ that I mentioned in Chapter 6. He began by considering any consistent set of rules of inference. Then he showed how to construct a proposition which could neither be proved nor disproved under those rules. Then he proved that that proposition would be true.
So my attempt to understand DD’s discussion of Godel’s incompleteness theorem will begin with a review of the relevant portion of Chapter 6, presented below:
DD opens the chapter with the question of whether we will be able to build a fully universal virtual reality generator which can render any environment the human mind is capable of experiencing.
DD clarifies that he’s talking about a virtual reality generator which could be programmed to generate all logically possible environments, and not something that would already contain within itself the specific instructions for generating the environment.
DD says we can imagine a virtual reality generator as having an effectively unlimited memory capacity for storing a given VR environment by imagining that it can read any number of disks.
DD says we can’t imagine unlimited computation speed like we can unlimited memory capacity. So what happens if the VR generator can’t render stuff fast enough??
DD says the answer is basically the VR generator would need to be able to control the equivalent of the brain’s “CPU clock” to keep it in sync with what the VR generator can generate. DD notes that this slowing down would be invisible from the user’s perspective within the simulation, though if their brain needs to be slowed down a bunch to make complex environments, more time will elapse in reality.
DD asks if there is anything outside the repertoire of a VR 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.
DD says the basic idea of the argument he will use, which is called the diagonal argument, has had various other applications, like proving that there are infinite quantities greater than the infinity of natural numbers, and to prove Godel’s Incompleteness Theorem.
DD says that each program for the VR generator has to have some particular, quantized set of values for any variables, and therefore “the set of possible programs must be discrete.”
Question: What’s the alternative here? Like what would a non-discrete set of possible programs mean?
DD says each program has to be expressible as a finite sequence of symbols in a 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.
Question: Is this similar to how there’s an infinite number of books that could be written but a finite length to any given book, cuz books are made up of sequences of letters represented in some physical objects (in ink on pages, or in a hard drive and then displayed on a screen) and you can’t have infinite actual letters?
DD says the requirements he’s been talking about — “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 a big deal that “impose drastic restrictions on the repertoire of any physically possible machine.”
DD asks us to imagine the infinite possible programs in an infinitely long list, numbered Program 1, Program 2, etc. You could also list them by VR environment they generate, so it’d be like Environment 1, Environment 2, etc.
DD says programs could vary a lot in how long they run for but let’s “consider only programs that continue to run for ever” to keep his proof simple.
DD says we can call the class of logically possible environments Cantgotu environments. He defines Cantgotu environments in the following way:
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 i. During the second minute it behaves differently from Environment 2 (though it is now allowed to resemble Environment i again). During the third minute, it behaves differently from Environment 3, and so on.
The “and so on” means that it behaves differently than all the Environments on our infinite list of programs the VR generator can run at some point.
Questions: How can we reason about these Cantgotu environments at all? What makes them logically possible? Do they necessarily contradict one or more of the requirements DD mentioned about programs being quantized in a finite number of symbols, etc? So the idea is these are programs which are physically impossible but which we don’t have any criticism of on logical grounds?
DD says that there’s a ton of Cantgotu environments possible, because the only constraint is that during some minute they behave differently than something in the list of programs the VR Generator can run.
DD says his argument shows that we can only run an infinitesimal fraction of the set of all logically possible environments.