Hi Max, in this particular universe it's going well, thank you!
As promised, I had a look at your paper. I think it is well written and fun to read. I've got a few comments though, mostly on the nature of math vs computation, and why Goedel is sexy but not an issue when it comes to identifying possible mathematical structures / universes / formally describable things. I think some of the comments are serious enough to affect the conclusions. Some come with quotes from papers in http://www.idsia.ch/~juergen/computeruniverse.html where several of your main issues are addressed. Some are marked by "Serious". I am making a cc to the everythingers, although it seems they are mostly interested in other things now - probably nobody is really going to read this tedious response which became much longer than I anticipated. 1. An abstract "baggage-free" mathematical structure does not exist any more than a "baggage-free" computer - the particular axiomatic system you choose is like the set of primitive instructions of the computer you choose. Not very serious, since for general computers and general axiomatic systems there are invariance theorems: changing the baggage often does not change a lot, so to speak. But it should be mentioned. 2. p 11: you say that data sampled from Gaussian random variables is incompressible - NOT true - give short codes to probable events (close to the mean), long codes to rare events (Huffman coding). 3. same sentence: how to test what inflation predicts? How to test whether the big bang seed was really random, not pseudo-random? The second million bits of pi look random but are not. We should search for short programs compressing the apparent randomness: http://www.idsia.ch/~juergen/randomness.html 4. p 15: Mathematical structure (MS) "just exists". Is that so? Others will look at your symbols and say they are just heaps of chalk on a blackboard, and you need a complex, wet pattern recognition system to interpret them. Here's where beliefs enter... 5. p 18: "mathematical structures, formal systems and computations are aspects of one underlying transcendent structure whose nature we don't fully understand" But we do! I'd say there are NO serious open problems with your figure 5 - formal systems vs math vs computation is a well-explored field. More about this below. The 2000 paper (your nr 17) exploits this understanding; it turns out the most convenient way to deal with the measure problem is the computer science way (right hand corner of your figure 5). As I wrote in the 2000 paper: http://arxiv.org/abs/quant-ph/0011122 The algorithmic approach, however, offers several conceptual advantages: (1) It provides the appropriate framework for issues of information-theoretic complexity traditionally ignored in pure mathematics, and imposes natural complexity-based orderings on the possible universes and subsets thereof. (2) It taps into a rich source of theoretical insights on computable probability distributions relevant for establishing priors on possible universes. Such priors are needed for making probabilistic predictions concerning our own particular universe. Although Tegmark suggests that ``... all mathematical structures are a priori given equal statistical weight'' [#!Tegmark:98!#](p. 27), there is no way of assigning equal nonvanishing probability to all (infinitely many) mathematical structures. Hence we really need something like the complexity-based weightings discussed in [#!Schmidhuber:97brauer!#] and especially the paper at hand. (3) The algorithmic approach is the obvious framework for questions of temporal complexity such as those discussed in this paper, e.g., ``what is the most efficient way of simulating all universes?'' 6. Serious: run the sim, or just describe its program? Are you sure you know what you want to say here? What's the precise difference between program bitstrings and output bitstrings? The bitstrings generated by the programs (the descriptions) are just alternative descriptions of the universes, possibly less compact ones. You as an external observer may need yet another program that translates the output bits (typically a less compressed description) into video or something, to obtain the description your eyes want. Note that the 2000 paper and the 2002 journal variant don't really care for time evolution, just for descriptions - within the bitstrings maybe there is an observer who thinks he knows what's time, but to the outsider his concept of time may be irrelevant. (Unlike the 1997 paper, the 2000/2002 papers do not focus on a one to one mapping between physical and computational time steps, otherwise we'd miss all the universes where the concept of time is irrelevant.) Here's what I wrote at the end: "After all, algorithmic theories of the describable do encompass everything we will ever be able to talk and write about. Other things are simply beyond description." 7. Serious: p 18 CUH: what's your def of computable? You mean by halting programs? In theoretical CS there are these famous computability hierarchies, and one should understand them to see the relation between math and computability (also in your figure 5): Halting-computable is just a tiny part of what's limit-computable, but limit-computable still means constructively describable. This was a major motivation of the 2000 paper, which identified all the constructively describable mathematical structures, i.e., those whose descriptions can be generated by (possibly non-halting) finite programs such that each description prefix does not change any more after finite time. (But you cannot predict when it will cease to change, otherwise you could solve the halting problem - but that's not an issue, just like the whole Goedel stuff is fun but not at all an issue - more on that below). 8. Serious: p 19 your cite of 13, 17 (the 97 paper and the 2000 paper) is misleading: Yes, I do mention halting universes in the 1997 paper (mostly because of the sexy coding theorem for halting programs), but even then I emphasize the importance of non-halting programs (since you'd miss out on a lot of constructively describable universes without them). And the 2000 paper is really driven by a few new insights about the nature of compressibility through non-halting programs, clarifying which universes and math structures are constructively describable, and which are not (and thus cannot exist even under the most relaxed constructive perspective). (Less relevant to what you are discussing: in certain algorithmic TOEs computation time plays a major role - the harder something is to compute, the smaller its probability. This is more restrictive (and perhaps more interesting) than the general case above which is discussed at length. Novel insights concerning the general case eventually ended up in the 2002 IJFCS article novel insights concerning computation time in the 2002 COLT paper http://www.idsia.ch/~juergen/speedprior.html ) 9. p 19/20: careful with Goedel - inconsistent is not the same as omega-inconsistent. BTW, inconsistent axiomatic systems correspond to systematic theorem provers (programs) listing all possible theorems, halting once the first contradiction is discovered. Desirable alternative: this search program does not halt. Non-halting programs can be good... 10. Serious. p 20 conclusion of C: IMO this focus on halting computations is missing the point. Non-halting computations are still constructive. If you want to talk about all constructive MS / universes you don't want to ignore universes compactly describable by NON-halting programs! One of the main points of the 2000 paper. 11. Serious. p 21 item 4: Goedel-undecidability: the 2000 paper is full of Goedel-undecidable yet limit-computable examples of mathematical structures / computable universes. Note that you don't really need infinitely many steps to compute any prefix of any limit-computable universe - you can do it in finite time, you just don't know at which point you're done! That's essentially all Goedel & Turing say. That's why Goedel does not pose any obstacles whatsoever when the question is: which are the formally describable universes? Some of those universes do allow for observers formulating undecidable questions - so what? As I wrote in the 1997 paper: http://www.idsia.ch/~juergen/everything/ "Although we live in a computable universe, we occasionally chat about incomputable things, such as the halting probability of a universal Turing machine (which is closely related to Gödel's incompleteness theorem). And we sometimes discuss inconsistent worlds in which, say, time travel is possible. Talk about such worlds, however, does not violate the consistency of the processes underlying it." 12. Serious. p 21 item 5: "even more general structures" - but you cannot describe them constructively at all! For example, most real numbers don't exist in the sense that you cannot describe them formally. Even the uncountability of the entire set of real numbers is not a formal consequence of the axioms of the real numbers but just a matter of interpretation - the axioms do not imply uncountability! They also have a countable model. As I wrote in the 2000 paper: Much of this paper highlights differences between countable and uncountable sets. It is argued (Sections 6, 7) that things such as uncountable time and space and incomputable probabilities actually should not play a role in explaining the world, for lack of evidence that they are really necessary. Some may feel tempted to counter this line of reasoning by pointing out that for centuries physicists have calculated with continua of real numbers, most of them incomputable. Even quantum physicists who are ready to give up the assumption of a continuous universe usually do take for granted the existence of continuous probability distributions on their discrete universes, and Stephen Hawking explicitly said: ``Although there have been suggestions that space-time may have a discrete structure I see no reason to abandon the continuum theories that have been so successful.'' Note, however, that all physicists in fact have only manipulated discrete symbols, thus generating finite, describable proofs of their results derived from enumerable axioms. That real numbers really exist in a way transcending the finite symbol strings used by everybody may be a figment of imagination -- compare Brouwer's constructive mathematics [#!Brouwer:07!#,#!Beeson:85!#] and the Löwenheim-Skolem Theorem [#!Loewenheim:15!#,#!Skolem:19!#] which implies that any first order theory with an uncountable model such as the real numbers also has a countable model. As Kronecker put it: ``Die ganze Zahl schuf der liebe Gott, alles Übrige ist Menschenwerk'' (``God created the integers, all else is the work of man'' [#!Cajori:19!#]). Kronecker greeted with scepticism Cantor's celebrated insight [#!Cantor:1874!#] about real numbers, mathematical objects Kronecker believed did not even exist. 13. Serious: p 21 conclusion of D: "a mathematical object does not exist unless it can be constructed from natural numbers in a finite number of steps - this leads to item 3". Careful here! Any finite thing can be computed by a halting program, of course. But do you want to forbid infinite descriptions whose every prefix is limit-computable in finite time? Then you'll lose many constructive mathematical structures of the 2000 paper! The most general constructive way to handle all descriptions really is the one mentioned above: Universe descriptions can be finite or infinite, but their shortest descriptions have to be finite. These shortest descriptions, however, may correspond to NON-halting programs that compute each prefix of the possibly infinite "unfolded" description in finite time, such that it remains stable thereafter, although you may never know WHEN it's converged (because of Goedel, but that's not at all important here). Ah, I am in a loop, repeating myself... 14. p 21 E: "no aspect of our universe is undecidable..." This does not seem true: build a computer in our universe, feed it with programs - it's generally undecidable by a halting program which ones will halt - so there are undecidable aspects of our universe. My old point: so what? This won't destroy our universe. 15. Serious. p 22 measure of computer programs: "they depend on the representation of structures or computations as bitstrings, and no obvious candidate currently exists for which rep to use". This is misleading. The measures for different but fundamentally equivalent computers / programming languages / axiomatic systems are the same save for multiplicative constants independent of the objects to be measured, because of the invariance theorems! 16. p 22 G: equivalence classes - measure problem: This is why those famous coding theorems are essential. A good coding theorem says: ok, there are many descriptions of a particular universe, but its measure is dominated by the probability of the shortest programs. Coding theorems for halting programs and certain types of non-halting ones differ a bit though. One must carefully state one's assumptions: which computable universe descriptions are acceptable as TOEs? Just the halting ones? Certain types of limit-computable ones (there are various more or less general classes)? Then check the corresponding coding theorem to deal with the measure problem. 17. p 23 main results: "we found it important to define mathematical structures precisely." well, that's a main motivation of the 2000 paper: what precisely does it mean to be formally describable? Answer (see above): the constructively describable mathematical structures (or formally describable things) are those whose descriptions can be generated by (possibly non-halting) finite programs such that each description prefix does not change any more after finite time. (I told you I am in a loop...) 18. p 23 "it is unjustified to identify the 1-dim comp sequence with 1 dim time." Sure - who's arguing against that? Ok, that's much more than I wanted to write originally. Hope it will help! Cheers, Juergen http://www.idsia.ch/~juergen/computeruniverse.html On Apr 14, 2007, at 2:49 AM, Max Tegmark wrote: > Hi Jürgen, > > I hope the universe is treating you well. > If you're looking for a new and better sleeping pill, you'll be > pleased to know that, after 11 years of procrastination, I've finally > finished http://arxiv.org/pdf/0704.0646. It's the sequel to that old > Level IV multiverse paper of mine, attempting to flesh out the ideas > and elaborate on implications. I've tried to elaborate on the many > interesting connections with your ideas, and I'd very much appreciate > any comments you may have - especially since you're one of the very > few people I imagine may read it! > > Cheers, > Max > ;-) --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to [EMAIL PROTECTED] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---