# David Deutsch says "number of atoms in universe is finite", but then says "number of programs of all finite lengths is infinite". Contradiction?

From the book "Fabric of reality" by David Deutsch.

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

So, why the list of programs is infinite if the length of each program is finite?

Namely “one can contain only a finite number of symbols” contradicts “There are infinitely many such programs”

The number of programs of all finite lengths is infinite. This is depressingly easy to prove. In C++, take the programs which (apart from decoration) say x=1, x=2, x=3,… (and so on for ever) and you have your infinite list of programs.

But if “one could not manufacture an infinite number of [configurations of matter]” then x cannot be infinitely big

P.S. also, it means that energy in universe is finite, and one day we will spend all energy of universe and die, since humans are robots

• Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on Computer Science Meta, or in Computer Science Chat. Comments continuing discussion may be removed. Dec 18, 2023 at 23:17

A good analogy would be the integers: There is an infinite amount of finite integers. We can prove that by contradiction: Let's say there was a largest finite integer $$i$$, then $$(i+1)$$ would be even larger and still finite. So there is no finite limit. A very similar argument can be made for computer programs by appending another statement instead of adding $$1$$.

Clearly, programs larger than the number of the atoms in the universe are impractical. And there are even much smaller programs that will run longer than the universe will exist (without running eternally). But that is kind of the point of David Deutsch's statement.

• Countable may be a better word than "finite" here. The set of integers is countably infinite. The set of real numbers, or even any arbitrary subset of it, like "all real numbers between 0.0 and 1.0", is uncountably infinite. Both infinite, but with an extreme difference in magnitude. Though also the initial assertion is a bit dubious. They're using x=1, x=2, x=3,… as an example of countably infinite programs, but...C++ doesn't do arbitrary-precision integer literals, so the proof doesn't work. At least, not as articulated there. There's only UINT_MAX programs in that sequence. Dec 11, 2023 at 4:48
• @aroth: "Countable" is a synonym for "finite or infinite of the smallest size", not "finite" – all integers are finite, there are countably infinitely many of them. I think invoking countability here doesn't add anything; you only need the finite/infinite distinction. And re. C++: the sequence is trivially modified to x=1, x=1+1, x=1+1+1, etc. Or even simply x=1;, x=1; x=1;, x=1; x=1; x=1 etc. Or you could implement a bignum library and do x = bignum(1), x = bignum(1) + bignum(1), x = bignum(1) + bignum(1) + bignum(1), etc. Dec 11, 2023 at 7:18

The key distinction here is that a program is a concept. A concept is distinct from the place that concept is represented or stored.

You can have the same program represented by different physical chunks of matter. The program print("Hello World") is the same program whether it is stored on my computer or on yours.

You can have the same program represented by arrangements of matter in different ways: it is the same program whether it's magnetic wobbles on a floppy disk of physical wobbles on CD, or even blobs of ink on a page.

Meanwhile if I take the exact location on my hard drive where the binary code is stored and overwrite the file, I have destroyed that physical representation of the program but I have not erased the concept itself.

Now, if you'll allow that the program as a concept can survive the destruction of its physical representation, then you might start to imagine the program as a concept even if it has not been represented at all. For example, I might meaningfully talk about the program that I'm trying to write, as a concept, but it hasn't been written yet. Even the neurons in my brain have just the vague outline of what the finished program ought to be. Even so, I can talk about it, saying how it should behave and even how it's different from another similar buggy program which I'm trying not to write!

Now, if the program as a concept does not need to have been written down in order to exist, it may then make sense that it does not need to be possible to write it down. So for example, I can meaningfully talk about "A program which does a physics simulation of a universe like ours except with a googol particles in it." Since we don't have a googol particles in our universe, there is no way that we could ever actually build a computer able to store and run that program. But we can talk about it, as a meaningful concept. We can even imagine that if we only had a bigger universe, then we could build a big enough computer!

From there, it's only the slightest jump to consider that there's infinitely many such programs which are finite in length (they could be written down given a big enough universe) even though our actual universe is too small.

• I should probably acknowledge that this answer probably wouldn't pass muster on the philosophy site, as I've been a bit sloppy in talking about concepts "existing" apart from the physical world as though in a Platonic sense. That is a very old controversy. Even so, I hope the illustration should still be helpful. Dec 9, 2023 at 21:29
• Minor point, but "A program which does a physics simulation of a universe like ours except with a googol particles in it." probably can be written, and would probably fit on a thumb drive. The issue is with having the memory to run it. Dec 10, 2023 at 20:22
• @SriotchilismO'Zaic, that's fair. I was going to add "From a given initial state" or something, but I stripped it back as I felt that level of i-dotting distracted more from the overall sense of the illustration. Dec 10, 2023 at 20:45

Because the number of possible lengths is infinite.

Consider the set of all possible sequences of the 26 upper case letters of the English alphabet, for all possible lengths of such a sequence.

The possible symbols in each sequence in such a set are themselves a finite set. There are only 26.

The possible lengths, though, are infinite, because the length can be any positive integer, and there is no ‘largest integer’ (you can always add 1 to an integer to get a larger integer).

Because the possible lengths are infinite, the set as a whole is also infinite. The same is true independent of how many possible symbols there are, as long as there is at least one possible symbol.

I understood now (after "program has a finite size") - this is "potential/unrealized vs actual/realized infinity" problem.

I, like Zeno in Zeno paradox with Achilles vs turtle, was thinking that something is an actual/realized infinity, while in reality it is potential/unrealized infinity.

Let me explain.

GIVEN only finite amount of matter is available to store programs AND list of programs is ACTUALLY (because it's a set like {1,2,3,...}) (countably) infinitely big AND each program is stored as FINITE string xxx where x is 0 or 1 =>

I was thinking in the end of list I will run out of space for xxx, but I will not, xxx is only POTENTIALLY (because it's a process like 1,2,3,...) (countably) infinite, xxx will never be ACTUALLY REALIZEDLY INFINITE, it will always be FINITE !! (it doesn't matter if our universe has finite or infinite amount of atoms or I need to build program from atoms in finite amount of time from finite amount of matter, I will not run out of building blocks)

Note: I say that xxx is both finite and potentially infinite. Is this a problem? TODO

UPDATE1: and then David Deutsch writes that each program creates virtual reality environment that can run finite or infinite time. Cangoto environments + cantgoto environments = all environments. Probably similar to: rational numbers (computable, set is countable , can be printed so that text have finite length) + irrational numbers (uncomputable, set is uncountable , infinite when printed, e.g. pi is a result of infinite computation like 1/(1+(2/(1+3/...)))) = real numbers

• Zeno's infinities of things are realized. They are just collectively finite. 1/2 + 1/4 + ... of the distance & time = the distance & time. Dec 10, 2023 at 8:23

Your reasoning is well-founded, but begins from different axioms than the ones Deutsch is using. The concern you're raising boils down to "how can any infinite set exist given there is only a finite amount of matter in the (observable) universe?" This is the line of inquiry that leads to mathematical finitism. L.E.J. Brouwer, for instance, would probably have said that it is impossible to write down the list of all Turing machines in a finite amount of time, even if supplied with infinite material to write on, therefore the idea of such a list is nonsensical.

It just means that it is not possible to write down all programs of finite lengths. You’ll probably run out of atoms at programs of length 200 or 300.