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 everything-list.domain.name.hidden
To unsubscribe from this group, send email to everything-list-unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Thu Apr 26 2007 - 10:31:45 PDT