I totally know what you mean!

I've been recommending this book left and right around these parts, but can't hurt to say it again: you should probably read "Permutation City."[1] As far as literature, character development and style goes, there is nothing much to it. As far as (hard-ish) scifi goes, it's a big deal. In a way, what MT calls MUH Egan calls "dust theory" (roughly). It's a very interesting exploration of the whole idea, and it involves cellular automata, etc etc.

There's also a short story of his, "Wang's Carpets" (which you can read online[2]) - it was later incorporated (as a chapter) into his book "Diaspora"[3] (which is also a great read that I've thoroughly enjoyed.)

> Although, to be fair to Tegmark, he goes further than I ever did: "The predictions of the theory take the form of probability distributions for the outcome of experiments, which makes it testable."

I wonder, though, if this is not a bit of a stretch. I certainly understand what he (and you) mean by probability distributions, but it seems to be there because he really wants to be able to call it a "scientific theory," which requires it to be falsifiable (<=> testable.) But, yeah, it's pretty neat!

> I was thinking maybe the probability of finding yourself in a given universe is related to the length of the computer program that runs that universe.

Now, can some of those programs run a (say, finite-tape-version-of) Turing machine[4] (can some of them not run it)? Does this have any implications (re: / in relation to the halting problem, for example)? I don't have the faintest idea. Tegmark has a thing to say about mathematically incomplete (in the Godel sense) universes, but again, I'm not sure how much of it is just him having fun. ;) (which is the best way of having fun, as far as I'm concerned.)

...anyway. Good stuff! Let's try and not go insane within our heads with these things. Then again, some insanity is always a good thing, imo.

edit P.S. there's also http://plato.stanford.edu/entries/computation-physicalsystem...

editedit P.P.S. if you haven't, maybe also read the (very) short story of Borges, "The Library of Babel."[5] It's basically an articulation of the idea that a "description" of a universe is that universe. And a "description" can very well be thought of as a program. And if you imagine a multidimensional "computational-symbol-space," a "path" to that program/description (first choose this symbol/predicate, then that one..) is that program (and, by extension, "kinda-is" that particular universe.) These ideas are not new in themselves in the very least. e.g. I'm still yet to try and honestly delve into Kant's "Critique of Pure Reason," which actually addresses some of that stuff (in its own very particular vocabulary and context.) Also, lots of stuff to read from the theoretical CS side of things. And mathematics (Yoneda lemma in category theory, and other things which I like to pretend to understand!)

[1]: http://en.wikipedia.org/wiki/Permutation_City

[2]: http://bookre.org/reader?file=222997

[3]: http://en.wikipedia.org/wiki/Diaspora_(novel)

[4]: a good read (and/or rehash) on this: http://plato.stanford.edu/entries/turing-machine/

[5]: http://jubal.westnet.com/hyperdiscordia/library_of_babel.htm...