![[photo courtesy of the multimedia lab machines]](http://www.doc.ic.ac.uk/~ids/dotdot/misc/images/ids_cropped.jpeg)
Iain Stewart
<ids@@doc.ic.ac.uk>,
Department of Computing,
Imperial College,
London, UK
The infinitude of the primes has been known since ancient times thanks to Euclid's reductio ad absurdum proof. Here's what I think might be a new proof of this ancient theorem. It's based around the concept of Kolmogorov-Chaitin algorithmic complexity, specifically as embodied in the so-called "incompressibility method". It may thus be of interest in that it can be added to the growing gallery of proofs that use algorithmic complexity concepts to solve problems whose subject matter is different from the "usual" or "canonical" sort of examples one traditionally comes across in presentations of the theory of algorithmic complexity. Star attractions recently added to this gallery include the proofs by Tao Jiang, Ming Li and Paul Vitanyi concerning a triangle problem of the Heilbronn type (math.CO/9902043) and a lower bound on the average-case complexity of shellsort (cs.CC/9906008). Their proofs are of wholly new results; mine is just a new proof of an old result I'm afraid - but I hope it may still be of some value, in particular for "getting a feel" for the ways the incompressibility method can be applied in varied and diverse problem-solving contexts.
Like all the best ideas, the incompressibility method is really quite simple. It comes in various versions: for our purposes here we really only need a cut-down version, as follows. Imagine you already know, by a counting argument or whatever, that there are at least 2 to the power N members of some class. Now suppose that some proposition Prop would imply that these members can all be coded by binary strings of length less than N. By "coded" we mean that there's an algorithm (the encoding algorithm, let's call it) mapping objects of the class to strings of length less than N, such that distinct objects always map to distinct strings. It's quite all right if the encoding algorithm is non-deterministic, so long as it always gives some string as an answer, and distinct objects always map to distinct strings. (In summary: the encoding algorithm, regarded as a multifunction relation from objects to strings, is to be total and nowhere many-to-one.) The coding is then invertible, that is, there is a deterministic, onto (but not necessarily total) decoding algorithm from strings of length less than N to objects of the class, mapping each string which can occur as the output of the encoding algorithm back to the unique object that must have been supplied as input. We will say a string codes for or decodes to an object, with the obvious meaning.
Well then, if Prop implies the possibility of such a coding, then Prop must be false! For there are only (2^N)-1 binary strings of length less than N - the empty string, two strings of length 1, four of length 2, and so on up to 2^(N-1) of length N-1 - and each decodes to at most one object of the class, contradicting that all of the at least 2^N objects of the class have invertible encodings. Thus this version of the incompressibility method is a reductio ad absurdum proof of the negation of Prop.
The name "incompressibility method" comes from thinking of the coding as a compression to compact form of objects whose standard (uncompressed) extant form might be quite large. A fuller version of the method can involve such issues as seeking a limiting compression ratio as the size of an input object tends to infinity; taking into account the length of a purported compression or coding algorithm, considered as a program for some fixed universal Turing machine; and so forth. However, even the cut-down version above can be seen to be about incompressibility - it says you can't losslessly (invertibly) compress all members of some class to binary strings each of length less than the base-2 logarithm of the cardinality of the class.
We take Prop to be the proposition that there are only finitely many primes. I shall show that this would allow a very compact representation of the natural numbers - more compact than writing them in, say, decimal or binary notation. In fact, absurdly compact! So compact as to represent, for some (in fact any) sufficiently large N, the first 2^N natural numbers as binary strings of length less than N, whereupon the incompressibility method delivers the reductio ad absurdum that Prop must be false and there must in fact be infinitely many primes.
The fundamental theorem of arithmetic states that every positive natural number has a unique decomposition as a product of primes, some factors possibly repeated. (The empty product is permitted, and is taken to be 1, the identity for multiplication.) For our purposes, however, we don't need uniqueness - we just need the fact that every positive natural number has a decomposition as a product of primes, which follows immediately from well-foundedness (if the number is composite, split it into proper factors and then care about those factors: this splitting must bottom out, and you've got your decomposition).
Suppose there are only finitely many primes, say K of them. Then we can represent any natural number using the following notation. For zero we use a one-character symbol (we might as well choose 0). For a positive number, we decompose it into a product of primes, and write down for each prime the number of occurrences of that prime in the product - the power which that prime is raised to in the product. Naturally we use, recursively, this notation when writing down each of those powers. For packaging the K powers into a list we can choose any unambiguous notation. For now I'll use square brackets to start and end a list, and commas and whitespace to separate the elements. Taking for example K=5, with the only primes in the world supposedly being 2, 3, 5, 7 and 11, we get these representations of the first few integers:
zero 0 (our chosen symbol)
one [0,0,0,0,0] (the empty product)
two [ [0,0,0,0,0], 0, 0, 0, 0 ] (that's 2 being raised to the power 1)
three [ 0, [0,0,0,0,0], 0, 0, 0 ] (that's 3 being raised to the power 1)
four [ [[0,0,0,0,0], 0, 0, 0, 0], (that's 2 being raised to the power 2)
0, 0, 0, 0 ]
five [ 0, 0, [0,0,0,0,0], 0, 0 ] (that's 5 being raised to the power 1)
six [ [0,0,0,0,0], [0,0,0,0,0], (2 and 3 are each raised to the power 1)
0, 0, 0 ]
seven [ 0, 0, 0, [0,0,0,0,0], 0 ] (that's 7 being raised to the power 1)
eight [ [0, [0,0,0,0,0], 0, 0, 0], (that's 2 being raised to the power 3)
0, 0, 0, 0 ]
.
.
.
The reader will be forgiven for thinking this is not a very compact notation for the natural numbers! Nevertheless, it is in fact absurdly compact as intimated earlier. To perform a length analysis, let's first simplify and standardize the layout. We can obviously drop all the commas and whitespace, which are just a sop to human readability, without compromising the notation. Less obvious, but also true, is that we can drop the closing brackets - all the lists are of length K, so if you've read K list elements, you know you're finished! So we're down to two characters, 0 and [. This is convenient since it means the strings are then already "binary"; with more than two characters we'd get bogged down in tedious accounting of bits-per-character and the like. The stripped representations:
zero 0 one [00000 two [[000000000 three [0[00000000 four [[[0000000000000 five [00[0000000 six [[00000[00000000 seven [000[000000 eight [[0[000000000000 . . .
These, although confusing to a human reader, are perfectly unambiguous to the decoding algorithm, which (just as you'd expect) goes as follows: if the string is 0, the answer is zero; otherwise skip the [ symbol, then read and decode exactly K substrings, using recursive descent parsing with this algorithm as the decoding algorithm for the substrings, whereupon the answer is the product of the K primes raised to those respective decoded powers.
Now then! We perform an inductive length analysis on facts of the form "the first so-and-so-many natural numbers are all coded by strings of length less than such-and-such".
Base case: "The first one natural numbers are all coded by strings of length less than two." This is trivial since zero is coded by the string 0, of length 1.
Inductive case: "If the first N natural numbers are all coded by strings of length less than L, then the first 2^N natural numbers are all coded by strings of length less than KL." (K, remember, is our name for how many primes there are supposed to be.)
Proof of inductive case: To be among the first 2^N natural numbers is simply to be less than 2^N. Such a number must therefore have fewer than N factors of 2, let alone of any other particular prime, in a decomposition of it into prime factors. Thus all K powers of primes in the decomposition are less than N, and by the inductive hypothesis have codings of length less than L. The coding for our number thus has a length of the sum of those K lengths each less than L, plus one for the [ symbol - that is, a total length less than KL.
By induction, we see that the first 2^(2^...(2^(2^(2^2)))...) (tower of height T of iterated powers of 2) natural numbers are all coded by strings of length less than 2(K^T). That "tower of powers", by the way, is sometimes called "2 tetrated by T", tetration being iterated exponentiation in the same way that exponentiation is iterated multiplication, and multiplication is iterated addition.
Since tetration is far faster-growing than exponentiation, by taking T above large enough we can make the binary logarithm of 2 tetrated by T (which is just 2 tetrated by T-1 in fact!) larger than 2(K^T). The incompressibility method then gives us the reductio ad absurdum we crave: that Prop is false and there are infinitely many primes.
Here are some thoughts on where we might go from here in using the incompressibility method in number theory and related fields.
I'd be delighted to hear from anyone who succeeds in taking things further in these or any other ways. Good luck to anyone who tries their hand!
This corner of the web maintained by
Iain Stewart
<ids@@doc.ic.ac.uk>,
Department of Computing,
Imperial College,
London, UK
- add your own comments to this web page or any other for all to see!
(Only supported by some browsers, sometimes via an extension or the like.)
(If you're reading this from within IC DoC you can try Crit,
an earlier way to annotate the web.
)
Add your own comments to this web page (or any other!) for all to see via
CritSuite
d363 7
a369 5
(If you're reading this from within IC DoC you can try a local way to
)
@
1.16
log
@added my photo to the link to my home page.
@
text
@d362 9
@
1.15
log
@new title for the triangle area paper at the Los Alamos archive.
@
text
@d338 6
a343 1
Iain Stewart
@
1.14
log
@new preferred URLs for the Los Alamos archive and its local mirrors.
(Incidentally, there's a certain level of affectation on their part
with these new URLs - the hostname part is not in fact case-sensitive!)
@
text
@d39 1
a39 1
(math.CO/9902043)
@
1.13
log
@MAJOR REVISION:
* my thoughts on theories of everything -> my proof of the infinitude of the
primes using Kolmogorov-Chaitin algorithmic complexity.
Plus:
* better choices of logical vs. physical HTML styles.
@
text
@d39 1
a39 1
(math.CO/9902043)
d43 1
a43 1
(cs.CC/9906008).
@
1.12
log
@"Chaitin complexity" and cognates -> "Kolmogorov-Chaitin algorithmic complexity"
and cognates. (More historically accurate and fair to give joint credit!)
@
text
@d3 3
a5 2
Hello Max... I came across your paper "Is `the theory of everything' merely the ultimate ensemble theory?" (gr-qc/9704009) on the web. I found it by a rather circuitous route. For several consecutive years now, here at Imperial College Department of Computing, I've been supervising an undergraduate individual project on quantum computing (with Peter Knight of our quantum optics section agreeing to act as an occasional informal "extra marker" to patch over the fact that the whole thing's not really my field!). When looking through the recent papers in the quant-ph section of the Los Alamos archive, just to try and keep up with things as best I can, I came across a link to your website, and thence to your ultimate ensemble theory paper. (Since then, of course, your paper's been covered by New Scientist in their "anything goes" article of 6th June 1998, and become much more widely known.)
Well, it was a joy to read, and I'm glad someone's "thinking big" in this way! Have you come across John Leslie's semi-popular book "Universes"? It deals with many of the same themes - although the later parts drift into a sort of religious apology, which I don't find particularly useful. Anyway, I have some thoughts on various aspects of your paper, which I hope you might find interesting or thought-provoking. So here goes!
I think the biggest issue here is choice of an "ultimate prior". If I've understood things right you're proposing the "uniform prior" in all parameter spaces: but is this really well-defined? (For example, uniform, log-uniform, or uniform in the "arctan-log" mapping you use for convenience in your graphs, will all give subtly different conclusions [posteriors] in any given application of the Bayesian approach.)
Stepping one level further out so to speak, there's also the inevitable problem of how to be "uniform" in the space of mathematical structures you give a sample of in your Figure 1. The diagram is by necessity very heterogeneous - after all any sub-parts of it that form ordered chains (like "double fields", "triple fields", ...) either get cut off due to inconsistency, or else, if that doesn't happen, we'd probably choose to have drawn the diagram differently (e.g. having one box called "generalized fields" with an implicit internal parameter n giving the order "double", "triple" etc). Casting a bird's-eye view over the whole diagram, one shudders at what it could even mean to paint the diagram with a "uniform" ultimate prior!
I do in fact have a provisional suggestion about this. It's at least vaguely related to notions of Kolmogorov-Chaitin algorithmic complexity. However I'll leave it till further on, when it'll make more sense (I hope!).
Meanwhile, here's a dramatic instance of the problems an over-simple concept of "uniform" might cause. In your footnote 13 (page 24), you're discussing your earlier pessimism about the whole ultimate ensemble theory project, when you thought all integer space dimensionalities (or 3 upwards anyway) were likely to be habitable. But: imagine this had been true, i.e. all dimensionalities >=3 are habitable. (It might even be true! One can think of reasons why not all forces would necessarily be "inverse-(D-1)th law" and thereby lead to the stability problems you discuss. But more of that later.) What would the consequences be for your whole "category 1a TOE" philosophical project? I believe it's wrong to say they would have been the pessimistic consequences you feared. That is, it's wrong to say that when we opened our eyes and counted our space dimensions and got 3, we'd thereby falsify the whole category 1a TOE project. For consider this: if the category 1a TOE is true, and contains SAS-inhabited worlds of all dimensions (3,4,5,...), then every SAS opens its eyes, counts its space dimensions, and (falsely and pessimistically) concludes the category 1a TOE is falsified!!! For example, creatures who count their space dimensions and get 4384792698273462 would, if they took a "uniform" prior over the integers seriously, have to go on to say: "Gosh! 4384792698273462 is such a tiny number, out of all the integers! Gee, I guess that falisifies the category 1a TOE." You see the problem? The use of a "uniform" prior over the integers would condemn every one of those SASs to reaching a false conclusion. (Slogan: All integers are tiny! Or: All integers are untypically small!)
A further, more technical problem is that in probability theory as currently practiced (with its demand that probabilities can be normalized to add up to 1), a uniform prior over the integers or other countable discrete sets doesn't even exist. However, I think one could argue that this problem is a lesser one - maybe "God's probabilities" don't really have to be normalized to add up to 1! A strange thought.
(Note that a uniform prior over the reals, or R^3 or R^4 or whatever, strictly speaking doesn't make sense in today's probability theory either! The reason this doesn't cause a crisis in Bayesian probability theory is simply that usually the very first observation in an experiment immediately modifies this dodgy prior to a normalizable distribution. But the case above [SASs of all space dimensions opening their eyes and counting] is uncomfortably different in style.)
I'll give my own musings on how we might get round these problems of interpreting uniformity later on.
Gregory Chaitin's work on algorithmic (Kolmogorov-Chaitin) complexity provides an intriguing counterexample to your Figure 2. (I realize Figure 2 is just a qualitative graph, and also not particularly pivotal to the paper as a whole. But you might still be interested in my counterexample. It touches on deep issues of how to think about axiomatizations, models, and the like.)
Have you heard of Chaitin's constant capital-Omega? You have to fix on a particular universal Turing machine, but once you've done that, Omega is a perfectly definite constant, just like pi. Unlike pi, it's uncomputable. Worse: it's "maximally" uncomputable. That is, given the first n binary digits as an oracle, you'd still have no way (no Turing algorithm) of guessing the subsequent digits with a success rate different from 50%. Omega is "(incompressibly) random" in the jargon of algorithmic information theory - although it's not, of course, "random" in the broader sense of capricious or underdetermined: it's just as determined (once your favorite universal Turing machine has been fixed) as pi or e.
Omega is defined as the probability that the universal Turing machine will halt, given a semi-infinite input tape of bits chosen randomly by independent coin tossings. - I hasten to add that the definition can be given without using words like probability. I'm just choosing to give the definition as intuitively clearly as possible.
Omega has the fascinating property that there is a simple Turing algorithm (though with a ridiculously long run-time) which, if given the first n binary digits of Omega as an oracle, can then solve the halting problem(!) for "generic Turing machines" (i.e. programs-with-embedded-input for our fixed universal Turing machine to run) of length up to and including n. (Taking the limit: if the whole of Omega is available as an oracle, the halting problem for Turing machines is solvable. However, the halting problem for Omega-oracle-enhanced Turing machines is still not solvable, for the usual reductio ad absurdum reasons.)
Since Omega is incompressibly "random", any particular consistent formal system (say ZFC, or ZFC plus your favorite axioms of large cardinals) cannot give a correct ruling on more than a finite number of digits of Omega. Thus, one can add new axioms: "Axiom 729. The 729th digit of Omega is 1", and so forth - in such a way that one is genuinely strengthening the formal system's complexity (and power) at each point - in the full, strict sense that the algorithmic complexity of the set of axioms is rising - and yet the system remains consistent. Thus, the "cliff edge" of Figure 2 is not compulsory!
There's something disturbing about all this. It means that mathematical reality can pick out certain structures as "special" (what you might call low "definitional" complexity), like Chaitin's number Omega, but formal systems cannot attain the state of handling these structures competently and flawlessly (any particular formal system will have either incomplete or wrong embedded knowledge of the structure). Now of course we knew this all along because of Gödel's theorem, but Chaitin's work puts a new, embarrassing quantitative spin on all this. That is, after Gödel's theorem mathematicians could shrug and say "Well, who really cares that a few highly esoteric propositions, of the form only metamathematicians ever use, are undecidable?" But the digits of Chaitin's Omega are not of that form. They act as oracles for an intensely practical problem (the halting problem - which, if one is doing physics by simulation, is the question "does this system reach a stable state?" or the like), and there are aleph-null of them, and we can only know finitely many (0%) of them!
We might want to "loosen up" Figure 1 (the giant structure diagram), in the sense that formal systems are perhaps being awarded an unfairly pivotal role in the diagram - mathematical reality can be construed to go beyond the collection of all formal systems. On the other hand, I suppose this is the issue (the nature of mathematics; Platonism, formalism, etc) that no-one can quite agree on, or even decide how to argue about! I'm guessing that you were not necessarily saying to the world "Ich bin ein Formalist" by designing Figure 1 the way you did. Rather, you were "playing safe" by sticking to the structures that mathematicians of all persuasions would agree existed, or could be talked about as if they existed: (structures described by) formal systems. Have I guessed right?
Here's a way space dimensions greater than 3 could turn out to be inhabited after all, and even by "particle-based" SASs (rather than string-based or membrane-based or whatever). The idea is we don't have to take the "inverse (D-1)th law" as a compulsory force law in dimension D. It's true you get that when you use massless, non-self-coupling exchange bosons in (D+1)-dimensional QFT. But maybe the important (most macroscopically obvious) forces will not be those mediated by massless non-self-coupling bosons! For example, in (3+1)-dimensional QCD, the color force between quarks is something like constant, or direct-linear (anyway, something that leads to confinement). Maybe in a higher dimension, some important force could just happen to come out as inverse-square? That is, stronger than the "default" inverse (D-1)th power law, but weaker than those laws leading to actual confinement (like constant or direct-linear). "Atoms" (and molecules, including the big molecules we call planets!) built using that force would then have a stable discrete spectrum of negative (bound) energy levels. Chemistry, and so potentially life and SASs, could exist after all!
Now, maybe gravity, in the Newtonian limit when it can be thought of as a force at all, has to come out as the inverse (D-1)th law. (Is that right in classical GR, for D>=3 anyway? I don't know offhand.) But even that need not be a problem. First of all, gravity might always be weaker than some other force(s) of the non-"default" sort I discussed above, so that that cosmos would simply not be ruled by gravity. But even if inverse (D-1)th law gravity was dominant on "solar system and above" scales, so that there were no stable planetary orbits around a central star, all hope is not lost. As one purely illustrative scenario: Take a cosmos with plenty of "stars", each stably bound because the details of the "intra-star structure" happen to involve a broad spectrum of the available forces - not just gravity but perhaps the mutual attraction of "charged" or "colored" layers or patches or whatever, some of the forces of which are inverse square or otherwise suitable for stability. (This is something like the way in our cosmos, a solid rock can spin faster than its own equatorial orbital velocity. It stays together because messy non-gravitational forces - chemistry, adhesion, mechanical cohesion - dominate gravity on its scale.) Now, beyond those stars with their stable intra-star structure, out into the scale where only gravity is important, there are indeed no stable planetary orbits. But suppose there are enough stars, or that sufficiently many of them burn brightly enough, that general interstellar space is at a comfortable ambient temperature for life. (Not an outrageous assumption! Even in our cosmos, the ambient temperature in big globular clusters or galactic centers can be tens of Kelvin.) Well then, a planet that simply wanders around in interstellar space could evolve sunlight-driven life. Eventually by bad luck it would crash into a star, but of course this is irrelevant if the timescale for this happens to be longer than that for Darwinian evolution.
Another route. Who needs stars?! (I think you are sympathetic to this question, as you hint in a few places, e.g. "it is unclear how necessary this is for SASs" on page 15.) Imagine the messy non-gravitational forces in our D-space cosmos do include suitable ones to let planetary bodies condense from a cloud and stay in one piece, but don't include decent analogues of our star-powering processes (nuclear fusion, gravitational contraction). Even then, all hope is not lost: so long as we have chemistry, we can have things like the earth's hydrothermal vents on these planets, and depending on the precise details of a planet's heat of formation, heat conductivity, radioactive element load and the like, the surface (or a layer below the surface) might be held at "room temperature" (SAS-supporting chemistry temperature) for a very long time.
So basically, I am much more cheerful about the habitability of higher-dimensional spaces than you are in your paper. Furthermore, as I said in my stuff about Bayesian inference above, I believe that, if this cheerfulness proves well-founded, it is not really a problem for the category 1a TOE - your pessimism in that scenario is misplaced. We can have our cake and eat it here!
On page 15 you mention the possibility that the values of the coupling constants could turn out to be a solution to an "overdetermined" problem (more equations than unknowns). I think your own preference (mine too, incidentally) is for the alternative interpretation you mention immediately after that: that some of the supposed constraints are not really necessary for SASs, and our island is one of several in the "archipelago".
However, let's play devil's advocate, and suppose the coupling constants really are the solution to more equations than unknowns. What would the philosophical implications be? You suggest the following: "This could be taken as support for a religion-based category 2 TOE, with the argument that it would be unlikely in all other TOEs." I've a feeling you really just suggest this for completeness, but let's think about it anyway. I believe anyone who argued for a category 2 religion in this style would be quite wrong to do so, even in the dramatic case I'm considering (the "more equations than unknowns" case). Here's why.
Basically, my argument is as follows. The category 2 religion would presumably center around a "design argument". You know the sort of thing: "A god must have designed things so that those equations have the beautiful mutual intersection in one tiny island that they do." But what does this mean? How can a god "design" such an eventuality? If such an eventuality is true, it is a (very complicated) theorem of pure mathematics. Its logical status is the same as the theorem that the first 20 decimal digits of pi are 3.1415926535897932384. It is, ultimately, a tautology, albeit one not obvious to the intuition (at least, to human intuition, with its short "run-time"). That is, it's simply not open to design!
In fact let me go further. Imagine the opposite eventuality is true. That is, imagine there are more SAS-feasibility equations than unknowns in the general class of QFT-type theories with coupling constants, but that there isn't a beautiful mutual intersection - the graphs of the (in)equations go all over the place, and their intersection is empty. Now, speaking metaphorically, say you're an "SAS-loving god". You want to create an SAS-rich cosmos. This is your burning desire. It's Wednesday in heaven, and you've just had a gruelling Tuesday exploring the possibilities of broadly "classical" theories. You're extremely annoyed at the way that every simulation you tried on your heavenly Cray-1 kept running into problems. There was an ultraviolet catastrophe, or a "chaos catastrophe" (where classical atoms are never quite the same as one another, leading to no useful reproducible chemistry), or one damn thing after another. You're beginning to wonder whether you're going to be able to create an SAS-rich cosmos at all! But then a friendly angel says "Don't panic, try QFT-type theories instead."
Well! You fire up your heavenly Cray-1 again, and plod through the various coupling constants. To your chagrin, it's another wasted day in heaven. Another case of one damn thing after another! If the strong force is right for stellar lifetimes it's wrong for variety-of-elements; if the weak force is right for radioactive heat load inside planets it's wrong for stellar stability; and so on, ad nauseum. By Wednesday evening you're feeling like smashing your heavenly Cray-1 into tiny little pieces. Are you ever going to strike lucky with SASs? Classical theories don't support them, and (we're assuming here...) QFT-type theories don't support them either.
One must assume that on Thursday or whenever, you finally discover a theory of a third class, different from both classical and "QFT-type", which does support SASs. Perhaps the regime in question is "non-mathematical". (Although as you can maybe guess, I'm going to argue that such a statement is meaningless.) Anyway, with a burst of heavenly joy you create the relevant cosmos, and the SASs live happily ever after. What can those SASs conclude about their world, and about you (the god)?
Well, those SASs proceed to do science in their world. They study the stars, measure their brightnesses and spectra and chart their life-cycles; they study the chemistry of the stuff they're made of; they build theories. They (like us humans) go through a long period of false starts and retractions. They invent classical mechanics; they discover its faults; they invent QFT; they (this is important!) discover its faults. Because, of course, it is faulty! All choices of its coupling constants (by hypothesis) fail to give stars in the sky and SASs on the ground. So they have to move on. Maybe they eventually discover the very regime that you (the god) discovered "on Thursday". At any rate, whatever they discover, their process of discovery is that of seeking and studying the examples of regularity of structure in their world. That is, of doing "applied mathematics". And probably also of deliberately running ahead and studying the space of logically possible structures - doing "pure mathematics" - with the vague hope that some of those structures might match up with the stars in the sky and the SASs on the ground - that "pure mathematics" might unexpectedly become "applied".
The punchline to all this? Simply that, like the person who discovered that all their life they'd been speaking prose, those SASs can't not do mathematics! Mathematics is not separable from the rest of knowledge and wisdom. Similarly, when you (the god) whooped with heavenly joy that your new Thursday regime had enough regularity of structure (and of the right kind) to support SASs, you were doing mathematics. As Pauli said of a theory in some other context, the problem with a purported category 2 TOE is not that it's wrong, but that it's not even wrong! It just doesn't mean anything to say of a TOE that it's not mathematical. It's like saying it's not written in prose.
The original case, where (again) there are more SAS-feasibility equations than unknowns, and (we change back to...) they do have a beautiful mutual intersection, has an even more straightforward route to the same punchline. In the metaphor I'm using, on Wednesday in this scenario you do find the beautiful mutual intersection. (You really do find it - you don't design it! Of course this opens up the old controversy about whether mathematics is discovered or invented. I hope you'll agree that for the purposes of telling the story in my chosen metaphorical language, I have to at least speak "as if" mathematics is discovered.) With a sigh of relief you create the cosmos specified by that intersection, and go and have a well-earned rest. The SASs in that world also discover the mutual intersection that their lives depend on. (At least if it's computationally simple and tractable enough.) They gasp at its beauty, but nevertheless they'd be utterly wrong to conclude that this is evidence for a "category 2 TOE". For again, where exactly is the "non-mathematical" aspect to all this? It's precisely a fact of mathematics - the existence of that intersection in the abstract space of possible mathematical structures - that permits those SASs' very existence!
Apologies for the rather rambling and metaphorical style of argument above. I think you make essentially the same criticism of the concept of a category 2 TOE in section V F 2 (page 25: "The generality of mathematics"), without the rambling style and without the dodgy theistic metaphor!
As promised, here's my (awfully tentative) proposal for how to re-interpret "uniform" either on the whole Figure 1 space of mathematical structures, or on the more limited "parameter space" within any one of them. Take first a parameter space. As an example, I'll use the same one as I used when I argued you were unduly pessimistic about the usefulness of a category 1a TOE if it turns out dimensions higher than 3 are all habitable. Namely, we're fixed inside some "box" of Figure 1 (e.g. a box called "QFT-like theories in any dimension"), and we're considering how to run over the parameter space within that box (the integer number of dimensions - leaving aside coupling constants [not to mention number of coupling constants!] in the interests of manageability).
My proposal: don't try to use a literally uniform prior over the integers. That leads to the false pessimism I outlined before. Instead, consider the Kolmogorov-Chaitin algorithmic complexity (in bits) of each potential parameter value (i.e. each integer). This is the length of the shortest program that prints the integer and nothing else and halts. - OK, this does depend on fixing a particular universal Turing machine, and a particular notation for output; but Chaitin and others keep reassuring us that all the "important" or "beautiful" results of algorithmic information theory are invariant modulo such choices. I'll accept their reassurances for the sake of argument.
Define the weighting for each integer to be 1 over (2 to the power of its complexity). This is the probability that the integer (and nothing else) would be emitted by a randomly chosen program for our fixed universal Turing machine. (Actually that's not quite true. If we wanted to make it true by definition we'd want to add up "1 over 2 to the power of the length of..." every program that prints the integer and nothing else and halts. We might also want to somehow "smudge this" over the set of different original choices for the fixed universal Turing machine - if this would help reduce embarrassing dependence on a particular one, assuming this did turn out to be a problem after all.)
What are the properties of this weighting? First of all, it's a bona fide probability distribution in its own right: it adds up to a finite number. (In fact to Chaitin's Omega! - Or less, if our fixed notation is such that some outputs are regarded as not syntactically valid integers and hence rejected.) Thus it can be normalized to add up to 1. Secondly, small integers (and a tiny handful of large integers, namely those like 10^(10^(10^(10^(10^(10^(10^(10^(10^10)))))))) with a highly regular structure, i.e. a simple algorithm for producing them) have large weightings. Thus if all space dimensions are habitable but we live in dimension 3, this is not an embarrassment. The integer 3 has a large weighting all to itself!
Turning now to the problem of painting the whole of Figure 1 with a Bayesian prior: well, the same general idea applies. To be precise: We consider the probability that a randomly chosen program would produce (a formal specification or axiomatization for) a particular mathematical structure and then halt. This "punishes" those structures that are particularly complicated and ad hoc in nature. Only long (and so "unlikely") programs would specify such structures!
A pleasing aspect of this proposal is it renders harmless the subjective decision "one box or many?" one keeps meeting when drawing a diagram such as Figure 1. For example, do we have a box "(3+1)-dimensional QFT", another box "(4+1)-dimensional QFT", and so on? Or do we have one box "QFT-like theories in any dimension", with an internal parameter D giving the number of dimensions? It doesn't really matter. In both cases, to output the specification of (say) a 4384792698273462-dimensional field theory "costs" the same. Either we have one long program to do it "in one go", or we have a short subroutine specifying the axioms for "QFT-like theories in any dimension" and then a subroutine specifying the act of plugging in the magic number 4384792698273462. You can find in Chaitin's work various sorts of "covering theorems" that guarantee that the precise value of complexity assigned to a given digital object (output text) is not much changed by such "notational disputes". - I'm still slightly nervous that things are maybe not as clean and straightforward for this application as Chaitin promises, but there's at least the hope it'll all work out OK!
Note that to specify a category of structure, then a sub-category within it, then a sub-sub-category within that, etc, one "usually" (i.e. unless the "zooming rules" themselves have algorithmically compressible structure) just has to give a program whose length is near enough the sum of the lengths of the specifying programs at each stage. Under the "1 over 2 to the power of..." rule, the weighting then becomes near enough the product of the "local weightings" assigned at each level of zooming in. Thus the general look and feel, as it were, of a decently-behaved probability distribution is rendered successfully.
So there you are! What do you think? The trouble is, only researchers in our
far future (if ever) will be capable of seriously summing and integrating
over substantial swathes of Figure 1 in the manner of your section III,
equations (4)-(7).
Thus only they will really discover the truth about any purported good and
bad features of proposed weightings. For now we're really all
just guessing! But I thought you might find these thoughts interesting,
and who knows, perhaps suggestive of something better.
d337 7
a343 7
This corner of the web maintained by
Iain Stewart
<ids@@doc.ic.ac.uk>,
Department of Computing,
Imperial College,
London, UK
d347 8
a354 8
Add your own comments to this web page (or any other!) for all to see via
CritSuite
@
1.11
log
@spelling correction.
@
text
@d92 2
a93 2
related to notions of Chaitin complexity. However I'll leave it till
further on, when it'll make more sense (I hope!).
d158 1
a158 1
work on algorithmic complexity provides an intriguing
d516 3
a518 2
the Chaitin complexity (in bits) of each potential parameter value
(i.e. each integer). This is the length of the shortest program that
@
1.10
log
@whoops! missed a wording that dated it as belonging to a specific era
(the time of my original message). Now "tweaked away".
@
text
@d86 1
a86 1
what it could even mean to paint the diagram with a "unifiorm"
@
1.9
log
@clarified I'm talking about Omega written in binary when I talk about
trying to predict its digits with a success rate different from 50%.
@
text
@d31 1
a31 1
I found it by a rather circuitous route. In the academic year just finished,
d36 1
a36 1
agreeing to act as an informal "extra marker"
@
1.8
log
@whoops! missed an obvious candidate for hypertext markup.
@
text
@d170 3
a172 2
Worse: it's "maximally" uncomputable. That is, given the first n digits
as an oracle, you'd still have no way (no Turing algorithm) of guessing
@
1.7
log
@gave poor old Go:del a proper o-umlaut!
used boldface R as best surrogate for the fancy R that means "the reals".
@
text
@d82 4
a85 3
drawn the diagram differently (e.g. having one box called "generalized fields"
with an implicit internal parameter n giving the order "double", "triple"
etc). Casting a bird's-eye view over the whole diagram, one shudders at
@
1.6
log
@QUITE MAJOR REVISION:
* proper HTML-ifying at last!
Plus:
* links to places it seems reasonable to point to
* mentioned the New Scientist "anything goes" article of 6th June 1998,
which post-dates my original message of 28th September 1997
* got rid of stuff that's just clutter now that it's HTML-ified
* tweaked wording to avoid talk of it being an e-mail message, or belonging
to a specific era (the time of my original message)
* wording corrections and improvements generally.
@
text
@d135 2
a136 1
(Note that a uniform prior over the reals, or R^3 or R^4 or whatever,
d221 1
a221 1
Now of course we knew this all along because of Go:del's theorem,
d223 1
a223 1
That is, after Go:del's theorem mathematicians could shrug and say
@
1.5
log
@updated to conform to the new linking protocol as specified in the draft RFC
document for "Text-Search Fragment Identifiers", available at the crit.org
website. This is the protocol followed by the latest advertised version
of Crit (version 0.9.1).
(Basically "#'" -> "#:words:". So now you know!)
@
text
@d17 1
a17 1
(Adapted from a
d19 4
a22 6
message from me to Max Tegmark
giving my thoughts on his
ultimate ensemble theory paper.
At the moment "adapted" just means token HTML-ifying, updating of things like
my phone number, and minor tweakings.)
d26 5
a30 23
From - Sun Sep 28 20:30:49 1997
Return-Path: <ids@@doc.ic.ac.uk>
Delivery-Date: Sun, 28 Sep 1997 20:29:42 +0100
Received: from pigeon.doc.ic.ac.uk by swan.doc.ic.ac.uk with SMTP (PP);
Sun, 28 Sep 1997 20:29:34 +0100
Received: from motmot.doc.ic.ac.uk [146.169.5.4] by pigeon.doc.ic.ac.uk
with smtp (Exim 0.55 #3) id E0xFP2A-0005Pd-00;
Sun, 28 Sep 1997 20:29:38 +0100
Received: by motmot.doc.ic.ac.uk (Smail3.1.29.1 #1) id m0xFP29-0001LZC;
Sun, 28 Sep 97 20:29 BST
Message-Id: <m0xFP29-0001LZC@@motmot.doc.ic.ac.uk>
From: Iain Stewart <ids@@doc.ic.ac.uk>
Date: Sun, 28 Sep 1997 20:29:37 +0100
X-Mailer: Mail User's Shell (7.2.5 10/14/92)
To: Max Tegmark <max@@ias.edu>
Subject: about your ultimate ensemble theory paper...
X-Mozilla-Status: 0001
Content-Length: 28047
Hello... I came across your paper "Is `the theory of everything' merely
the ultimate ensemble theory?" (gr-qc/9704009) on the web.
d33 4
a36 2
undergraduate individual project on quantum computing (with Peter Knight
of our quantum optics section agreeing to act as an informal "extra marker"
d38 4
a41 2
When looking through the recent papers in the "quant-ph" section of the
Los Alamos archive, just to try and keep up with things as best I can,
d44 7
d52 1
d55 1
a55 1
It deals with many of the same themes---although the later parts drift into
d59 1
d64 1
a64 2
About the Bayesian inference approach:
--------------------------------------
d66 1
d73 1
d75 1
d79 1
a79 1
heterogeneous---after all any sub-parts of it that form ordered chains
d87 1
d89 1
d91 3
a93 2
related to notions of Chaitin complexity. However I'll leave it till later
in this e-mail, when it'll make more sense (I hope!).
d95 1
d102 4
a105 3
(It might even *be* true! One can think of reasons why not all forces
would necessarily be "inverse-(D-1)th law" and thereby lead to the stability
problems you discuss. But more of that later.)
d112 1
a112 1
worlds of all dimensions (3,4,5,...), then *every SAS* opens its eyes,
d117 1
a117 1
"Gosh! 4384792698273462 is such a tiny number, out of all the integers!
d122 1
d124 1
d126 1
a126 1
currently practiced (with its demand that probabilities can be normailized
d129 2
a130 1
*this* problem is a lesser one---maybe "God's probabilities" don't really
d132 1
d134 2
a135 1
(Note that a uniform prior over the *reals*, or R^3 or R^4 or whatever,
d142 1
d144 1
d147 1
d152 1
a152 2
About the axiomatization of mathematical structures:
----------------------------------------------------
d154 3
a156 1
Chaitin's work on algorithmic complexity provides an intriguing
d161 1
d163 1
d166 4
a169 3
a perfectly definite constant, just like pi. Unlike pi, it's uncomputable.
Worse: it's "maximally" uncomputable. That is, given the first n digits
as an oracle, you'd *still* have no way (no Turing algorithm) of guessing
d172 1
a172 1
theory---although it's not, of course, "random" in the broader sense of
d174 2
a175 1
universal Turing machine has been fixed) as pi or e.
d177 1
d180 1
a180 1
independent coin tossings. --I hasten to add that the definition can be
d183 1
d185 1
d187 3
a189 2
(though with a ridiculously long run-time) which, if given the first n
binary digits of Omega as an oracle, can then *solve the halting problem*(!)
d191 2
a192 1
for our fixed universal Turing machine to run) of length up to and including n.
d195 4
a198 2
problem for *Omega-oracle-enhanced* Turing machines is still *not* solvable,
for the usual reductio ad absurdum reasons.)
d200 1
d204 5
a208 5
Thus, one can add new axioms: "Axiom 729. The 729th digit of Omega is 1",
and so forth---in such a way that one is genuinely strengthening the
formal system's complexity (and power) at each point---in the full, strict
sense that the *algorithmic complexity* of the set of axioms is rising---and
yet the system remains consistent. Thus, the "cliff edge" of Figure 2
d210 1
d212 4
a215 2
There's something disturbing about all this. It means that *mathematical
reality* can pick out certain structures as "special" (what you might call
d217 1
a217 1
*formal systems* cannot attain the state of handling these structures
d226 1
a226 1
practical problem (the halting problem---which, if one is doing physics by
d230 1
d232 1
d235 1
a235 1
pivotal role in the diagram---mathematical reality can be construed to go
d245 1
d250 1
a250 2
About the prospects for SASs in other space dimensionalities:
-------------------------------------------------------------
d252 1
d256 5
a260 4
The idea is we don't have to take the "inverse (D-1)th law" as a compulsory
force law in dimension D. It's true you get that when you use massless,
non-self-coupling exchange bosons in (D+1)-dimensional QFT.
But maybe the important (most macroscopically obvious) forces will *not*
d266 1
a266 1
That is, stronger than the "default" inverse (D-1)th power law,
d272 1
d274 5
a278 3
Now, maybe *gravity*, in the Newtonian limit when it can be thought of as
a force at all, *has* to come out as the inverse (D-1)th law.
(Is that right in classical GR, for D>=3 anyway? I don't know offhand.)
d282 1
a282 1
But even if inverse (D-1)th law gravity was dominant on
d288 1
a288 1
available forces---not just gravity but perhaps the mutual attraction of
d294 1
a294 1
forces---chemistry, adhesion, mechanical cohesion---dominate gravity on
d308 1
d310 1
d314 3
a316 3
Imagine the messy non-gravitational forces in our D-space cosmos
*do* include suitable ones to let planetary bodies condense from a cloud
and stay in one piece, but *don't* include decent analogues of our
d324 1
d326 1
d331 3
a333 2
a problem for the category 1a TOE---your pessimism in that scenario is
misplaced. We *can* have our cake and eat it here!
d338 1
a338 2
About our "local island", and other islands:
--------------------------------------------
d340 1
d348 1
d350 1
d358 3
a360 2
I believe anyone who argued for a category 2 religion in this style
would be quite wrong to do so, *even in the dramatic case I'm considering*
d362 1
d364 1
d371 3
a373 2
*pure mathematics*. Its logical status is the same as the theorem that the
first 20 decimal digits of pi are 3.1415926535897932384.
d376 2
a377 1
That is, it's simply *not open to design*!
d379 1
d381 1
a381 1
That is, imagine there *are* more SAS-feasibility equations than unknowns
d383 2
a384 1
there *isn't* a beautiful mutual intersection---the graphs of the (in)equations
d398 1
d400 1
d403 1
a403 1
To your chagrin, it's *another* wasted day in heaven.
d409 1
a409 1
Are you *ever* going to strike lucky with SASs? Classical theories don't
d412 1
d414 1
d417 1
a417 1
which *does* support SASs. Perhaps the regime in question is
d422 1
d424 1
d430 2
a431 2
they invent QFT; they (this is important!) discover *its* faults.
Because, of course, it *is* faulty! All choices of its coupling constants
d436 1
a436 1
*process* of discovery is that of seeking and studying
d440 1
a440 1
structures---doing "pure mathematics"---with the vague hope that some of
d442 2
a443 1
ground---that "pure mathematics" might unexpectedly become "applied".
d445 1
d447 1
a447 1
all their life they'd been speaking prose, those SASs can't *not*
d451 1
a451 1
to support SASs, *you* were doing mathematics. As Pauli said of a theory
d453 2
a454 1
that it's wrong, but that it's not even wrong! It just doesn't *mean* anything
d457 1
d459 1
d462 1
a462 1
they *do* have a beautiful mutual intersection, has an even
d465 2
a466 1
(You really do *find* it---you don't design it! Of course this opens up the
d478 2
a479 2
It's precisely a fact of mathematics---the existence of that intersection
in the abstract space of possible mathematical structures---that permits
d481 1
d483 1
d488 1
d493 1
a493 2
And finally...
--------------
d495 1
d505 2
a506 2
(the integer number of dimensions---leaving aside coupling constants
[not to mention *number* of coupling constants!]
d508 1
d510 1
d513 1
a513 1
the *Chaitin complexity* (in bits) of each potential parameter value
d516 1
a516 1
--OK, this does depend on fixing a particular universal Turing machine,
d521 1
d523 1
d525 1
a525 1
1 over (2 to the power its complexity). This is the probability that the
d530 1
a530 1
*every* program that prints the integer and nothing else and halts.
d533 1
a533 1
fixed universal Turing machine---if this would help reduce embarrassing
d536 1
d538 1
d541 1
a541 1
(In fact to Chaitin's Omega! --Or less, if our fixed notation is such that
d544 2
a545 1
Secondly, *small* integers (and a tiny handful of large integers, namely those
d548 1
a548 1
have *large* weightings. Thus if all space dimensions are habitable
d551 1
d553 1
d562 1
d564 1
d569 2
a570 2
Or do we have *one* box "QFT-like theories in any dimension",
with an internal parameter D giving the number of dimensions?
d579 2
a580 2
by such "notational disputes". --I'm still slightly nervous that things are
maybe not as clean and straightforward for *this* application as
d582 1
d584 1
d588 2
a589 1
structure) just has to give a program whose length is near enough the *sum*
d592 2
a593 1
the *product* of the "local weightings" assigned at each level of zooming in.
d596 1
d598 1
d604 1
a604 1
bad features of proposed weightings. In 1997 we're really all
d607 1
a607 24
Yours sincerely,
Iain Stewart.
--
Iain Stewart
Dept. of Computing
Imperial College, London SW7 2AZ, U.K.
(+44) 20-7594-8349
ids@@doc.ic.ac.uk
http://www.doc.ic.ac.uk/~ids/
--
And on the sixth day God said "Bugger this! I'm going to re-compile the
universe *without* error checking."
---with apologies to Eric Fosdike <esf@@doc.ic.ac.uk>
@
1.4
log
@added a header to go with the title (I just forgot this earlier!).
@
text
@d18 1
a18 1
d21 1
a21 1
@
1.3
log
@whoops! even inside ..., "<" and ">" characters are subject to HTML meta-character interpretations. (Or at least the former is, but for clarity I'll deal with the latter too.) So: rendered them as "<" and ">" respectively, to avoid this. @ text @d12 3 @ 1.2 log @"max.mail" -> "my_thoughts.html": cut down to just my message to Max that started the thread; then, token HTML-ifying, updating of things like my phone number, and minor tweakings. @ text @d28 1 a28 1 Return-Path: