In a previous article, I reviewed some of the troubles ailing superstring theory, as chronicled by two prominent and articulate discontents. Among the more radical suggestions for fixing physics is to get away from continuous models altogether and ask if the universe is fundamentally a discrete entity in some way. Proponents of this view — called digital physics or nearly-equivalently, digital philosophy— take on not one but two terrifying tasks. Not only must they reconstruct centuries of physics built on top of calculus (a fundamentally continuous sort of math) but to finish the job at a satisfying level, take on continuum mathematics itself and reconstruct it in discrete terms. The debate has relevance even further afield, to questions about the nature of consciousness. I’ll talk about three books that develop this approach in an accessible manner, and about one formidable one that I think confuses the issues in pointless distracting ways.
In this first part, for the mathematical foundations, I’ll talk about Gregory Chaitin’s Meta Math!: The Quest for Omega
Meta-Math: Is the Real Line Real?
Chaitin, a rather famous member of the rather famous IBM T. J. Watson center, is best known for co-inventing, along with Kolmogorov, a measure of computational complexity called Kolmogorov-Chaitin complexity. You could say the entire book is about using this measure to probe whether the real line is actually real. Here is the gist of the idea.
Kolmogorov-Chaitin complexity measures the complexity of a bit string in terms of the length of the theoretical shortest program that could have produced it (actually determining whether a program is the shortest one is undecidable). This leads to an approach to complexity in computer science that is very different from the P/NP variety, called Algorithmic Information Theory (AIT). Like Shannon’s older information theory, AIT studies the information content of strings of bits, but comes up with different answers for reasons that I’ll explain in a minute. But the reason AIT ends up shedding light on foundational issues is that it can be used to frame a very interesting question about the halting problem version of Godel incompleteness. Instead of asking if a Universal Turing Machine (UTM) will halt for a given program/data input, you ask, given a random program of length p bits, what is the probability that the UTM will halt?
This probability is called Omega and is among the most mysterious numbers around, and the key to why you might believe that the real line is unreal. For fun, here is the formula for this (gratuitous use of my inline LaTeX WordPress plugin):
[tex]\Omega_F= \sum_{P\in P_F}2^{-|P|}[/tex]
But first some simple examples to provide background.
Shannon vs. Kolmogorov-Chaitin
Consider a string of a 1000 bits like 1010101010101010101…10. This sort of obvious repetitive pattern poses no problems. Shannon information theory (the stuff that runs under the hood of your file compression programs) would tell you there is very little content, and so would K-C theory (a 500 iteration loop that prints out ’10’ would do the trick). But now consider two other numbers; the first a true (not pseudo) random number produced by flipping a coin (heads=1, tails=0). It might look like:
10101001010101010100010101011111010110…
And consider this other number:
11.0010010000111111011010101000100010…
Shannon’s approach would, in general, conclude that there is 1 bit per bit of information in both strings (recall that Shannon information entropy is essentially a statistical measure of randomness that says nothing about hidden structure). But K-C would conclude that the latter has very low information content, because it happens to be the binary version of pi, a number which, despite having no discernible pattern, can nevertheless be produced by very short (if slow) programs. But for the former, K-C theory would do no better than a Shannon-driven compression engine, since the best program you could write for an arbitrary coin-toss sequence number would be something like
print “101010010101010101000101…”
which would be a constant longer than the output itself.
Getting to the Real Line
So what does all this have to do with the reality of the real line? The argument is tricky, but here is an outline, and begins with Kronecker’s famous assertion that “God created the integers, all else is the work of man.” Start with the assumption that the positive integers are meaningful constructs (corresponding to things like the number of cats in the room and so forth). Negative numbers find some physical manifestation in, say, electric charge (let’s not use the typical abstract example of financial debt). You get to rational fractions when you slice up pizza. Rational complex numbers, it turns out, are also quite meaningful for talking about things like quantum states. You can go quite a bit further into the irrationals. Though the whole set of irrationals is uncountable, interesting subsets are countable. For instance, the algebraic reals (roots of polynomials) like the square root of 2, are countable. Transcendentals though (which are provably not the roots of any algebraic equations with rational coefficients) are not.
But somehow, you’ll never actually get to something in the universe (sneak peek: except possibly consciousness) that corresponds clearly to the continuum. If you haven’t studied some point-set topology, this can be hard to appreciate, but here’s a quick peek at why this is so. Take the well-defined set of rationals, which constitute a countable set. Unlike the integers (or odds or evens), the rationals are somewhat strange. Though you can count them through clever tricks, in their natural state they behave strangely. Since, between any two rationals p and q, you can always find another rational (p+q)/2, no matter how much you “zoom in” on the real line, you won’t see the rationals embedded like pinpricks against a “continuous line.” The set of rationals will appear just as ‘continuous’ to you as the whole continuum. Unfortunately, you can use the exact same sort of analysis to conclude that it is plurality and discreteness that are illusory, which is what Zeno famously did, so it is to some extent a matter of making a leap of faith in one direction or the other.
The abstraction of the continuum that we think make sense actually falls apart upon scrutiny. Our instincts lead to absurdities. Perhaps you can find ways to make our intuitions of integers fall apart in similar ways, but I haven’t found any that are this compelling.
So if the intuition behind your sense of “continuous” falls apart with even such a simple probe, we have to doubt the foundations of the real line, and therefore our natural notions of continuous space and time. This is where Omega comes in.
It turns out that a lot of very crucial sets are countable, just the way the rationals are. This includes all computer programs written in a finite symbol alphabet, all programs shorter than a given length, and so forth. The implication: if the real line is real, it contains more numbers than all possible outputs (in binary form) of all computer programs. In other words, the set of all computable numbers (which is the same as all computable outputs, since any output can be converted into a bitstream) is countable. Some very curious results also follow. For instance the set of all nameable numbers (one, two, googol,…, pi, e,…) is also countable, and therefore almost all numbers are unnameable and uncomputable. Almost all here is a technical term from something called measure theory, which is easiest to understand as follows: if you pick a real number at random (say by tossing a coin at random forever), then with probability 1 it will be uncomputable and unnameable (I am oversimplifying a bit here, but I can’t reasonably summarize a highly incompressible and random book in one post!).
Omega is interesting because it appears to fit in that subtle zone of nameable but not computable. You can clearly define it as a property (stateable in some finite symbol system) but you can’t compute it. It is, in a sense, the first sign of the last frontier of knowable numbers. Beyond lies a ridiculously larger ocean of entities so elusive, you have to wonder, why keep them around in your conceptual framework at all?
Where to Next?
I’ll stop there for today, but here are some directions you can go from here (some of which I’ll go). You can take these ideas into physics and ask if the universe is random or pseudorandom, and whether space and time could be fundamentally discrete, which I’ll get to in Part II. You can continue probing within mathematics at these ideas, by looking at, for instance, the earlier ideas of L. E. J. Brouwer which I’ll get to if I ever understand them.
And finally, if you make certain precise analogies between these ways of parsing mathematics and phenomenal reality to constructs of subjective consciousness, you can create surprisingly (and suspiciously) close analogies to different sorts of metaphysics. A sneak preview: Buddhist sunya metaphysics appears to map to digital physics, while Vedantic Advaita appears to map to continuous-background theories. Plato’s Allegory of the Cave, which I am just starting to ponder, also seems to map, but I am not sure how (some help here?). A suitably abstracted metaphysics from existentialism seems to map to some sort of true-random physics. These are, of course, analogies among three sets of mysteries (mathematics, physics and consciousness) that may or may not amount to anything. But then, if I wanted to stay away from wild speculation, I’d have stuck to academic writing.
If you find someone who tries pull a sleight-of-hand “one mystery cancels an analogous mystery” stunt on you, kick him/her in the pants for me. I’ll cover the physics stuff next. It is late and I need to sleep.
About Venkatesh Rao
Since rationals are countable (i.e. I can assign an integer to any rational and say it is the nth rational), and can “appear” to be “as continuous as the continuum”, it follows — integers can also “appear” to be “as continous as the continuum”.
In my case, I think early on (6th – 10th grade) I struggled with the idea of the continuum, cause the concept of a point “adjecent” or “next” to another point doesnt make sense. It took me some time (11th – 12th grade) to get used to the fact that between any two points there are infinitely more points (and that too in an uncountable way). Then I stopped thinking after that, and now you want to swing me back to thinking that the concept of the “adjecent” point makes sense. Thats a bit too much I say ! ;)
As usual, thanks for all the pointers. Your articles are becoming increasingly link-rich. Keep ’em coming.
Here is one thought experiment with the concept of “adjecent” points.
Imagine an infinite collection of marbles, touching each other and arranged along a straight line. Now imagine the marbles shrinking…. shrinking and crowding together, such that the marbles always keep touching the adjecent ones. Let them shrink away to size zero. So what does this entire setup shrink to? A point? A line? I guess you could argue either ways.
THe starting point was really the set of integers. If it shrinks to a point, then is that what the set of integers is equivalent to? A point? If it shrinks to a line, how and when did the transcendentals creep in ? cause they cant really be any of the marbles themselves (marbles being countable). If you imagine that the marbles started shrinking at t=0 and shrunk to size 0 at t=1, then all the transcendentals appeared out of nowhere at exactly t=1.
Even though we may have all these problems with the continuum, why give up on it? why go digital? You could build models and play around…but the continuum will always haunt.
I think you can’t argue for the line of marbles becoming a line. It would become a point. If r is the radius, both 2r and 2nr converge to 0 in the limit. But yes, you can map the integers to an arbitrarily small part of the real line. Take for instance the sequence 1, 1/2, 1/3….1/n,…, which maps to (0,1].
I think the only good reason to keep the continuum around is this. Let’s agree with the problems highlighted by thought experiments and conclude that physical reality has no continuum aspect. Let’s go further and take as an article of faith what some physicists are claiming (namely that you can rewrite fundamental physics in discrete terms). So our sense that space is continuous (or time) is an illusion. But then, why is our fundamentally digital brain even capable of generating this particular illusion? Our retinal cells for a discrete (CCD like) array. Our visual cortex does a series of discrete image processing passes (segmentation, edge detection etc.), so why is our subjective perception capable of a continuity illusion?
One way to resolve this is to say that subjective consciousness forms a continuous background to thought. Even though the Cartesian theater is a flawed way of looking at mental perception, the idea that all consciousness has a “background” is not implausible.
Stumbling upon this thread while checking some material about a more recent post I want to add a very relevant reference against the appropriateness of the continuum idea (as we know it, i.e. the real line) for describing reality:
Does matter differ from vacuum? by Christoph Schiller.
But is not digital either, the real coordinates just “melt away” below some very small scale, hé, hé…
“… so why is our subjective perception capable of a continuity illusion?”
Is there really a case that we subjectively perceive a continuum (complete, hence uncountable, hence almost all un-nameable, etc.) of space rather than just something dense (i.e., not discrete)?
How would you even know the difference?
Since my training is in mathematics, I think I tend to consider the continuum (like most mathematics?) a useful and pretty fiction. Completeness is nice for lots of theorems. (As you note, there’s also a certain ugliness to it, but that’s fine.)
Nice article! I had been planning to write on something similar but from an inference perspective.
I only wanted to point out one thing in your articles about Digital Philosophy and Kolmogorov Complexity. It might just be a minor point.
But Ray Solomonoff’s contributions to Kolmogorov Complexity are as fundamental as are Kolmogorov’s and Chaitin’s. He approached the idea from Inductive Inference, Chaitin and Kolmogorv approached it from randomness. Infact Solomonoff wrote the first set of papers on the area.
Dear “kapsio” circa 5 years ago,
The integers DO shrink to a point, as do all countable sets, and hence can’t REALLY form lines. But the reals are utterly incompressible (possibly, maybe incomprehensible, too) and hence actually can fill a line, depending on your definition of actually.
The only chain of numbers (as points) that can actually “touch” are the real numbers. They have to be totally incompressible. Anything less and they collapse into a single point. Well, not quite. You can take out any countable set of points, shift the reals over to take their place, and go on as if nothing ever happened.
Unless you reject the continuum and continuous lines. I may be losing my mind here.
Hurrah, that’s what I was searching for, what a stuff! existing here at this website, thanks admin of this web page.