(This is a belated response to Jürgen Schmidhuber's post at
http://groups.google.com/group/everything-list/browse_thread/thread/ceae8b5488e1ae7d/bf9ee6a75c36b97c?lnk=gst&q=Schmidhuber&rnum=13#
)
Hi Jürgen,
Very belated thanks for taking the time to send all these detailed and
constructive comments, which helped improve the revised version at
http://arxiv.org/abs/0704.0646.
I got so inundated with comments from various people that I decided to
go through them all together once i got the referee reports, which
took an eternity.
I've written some more detailed comments below, but my main conclusion
from reading your comments is that I'd really enjoy getting to chat
with you about these issues in person at some point. On one hand, we
have seemingly very different views of physics and the sense in which
it which may be a computation, differences which probably require a
face-to-face chat to get to the bottom of. On the other hand, we have
certain views in common that are held by almost none of my physics
colleagues, i.e., that there's probably no true continuum in nature,
and these issues would also be great fun to discuss over a suitable
beverage.
On Apr 26, 2007, at 10:31, Juergen Schmidhuber wrote:
> 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.
It sounds like you're referring to formal systems here (defined using
axiomatic systems) rather than mathematical structures (defined by
relations). I'm not convinced that a mathematical structure like the
cube needs any baggage.
> 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).
Good point; I know better, and see in hindsight that I was sloppy when
I wrote that.
I've reworded the text to clarify this.
> 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
I certainly encourage searches for such extra regularities. However,
my best current understanding of the physics suggests that
none will be found. I think you and I have reached rather different
conclusions about the origin of quantum indeterminacy.
> 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 prediction
Although I'm a big fan of algorithmic information, and recently had
the honor of meeting Gregory Chaitin, I'm still not convinced that
all of these issues are satisfactorily understood. For example,
there's about a paper a month coming out now about attempts to solve
the measure problem in cosmological inflation and predict a
probability distribution for what cosmological parameters are seen by
observers like us,
yet pesky issues related to comparing infinite volumes continues to
plague all attempts I've seen.
I don't think you're claiming that you have an answer to that
particular problem, say.
> 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."
I'm afraid that there are still basic parts of your description of
reality that I fail to understand.
What's with "video"? How are your bit strings supposed to describe the
metric around a black hole or the wavefunction of the universe?
> 7. Serious: p 18 CUH: what's your def
> of computable? You mean by halting
> programs?
Yes.
> 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).
Thanks for pointing this out.
I've reworded the sentence to "Schmidhuber has hypothesized that all
halting programs (together with certain non-halting ones)
correspond to physical realities \cite{Schmidhuber97,Schmidhuber00}".
If you'd like me to word the reference differently, just let me know
how.
> (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?
For both 10 and 11, please note that I'm not trying to describe what
you refer to a universe (being "run"), but the relations that specify
a mathematical structure.
So any one relation must either hold or not hold, and if one lacks an
algorithm that can say which of the two it is in a finite time, it's
hard for me to see in what sense one could still argue that this
relation is well-defined in practice.
> 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."
Here you and I fully agree (indeed, this is why I wrote "this point is
also emphasized in \cite{Schmidhuber00})").
> 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.
I totally agree - that's why I say that I'm dubious of item 5.
> 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.
Indeed - as a corrollary of the Löwenheim-Skolem Theorem.
> 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.
Indeed! You are one of the very few people I know of (besides myself)
who hold
this heretical view.
> 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!
Oh, that sentence isn't supposed to express my view, merely the
finitist view expressed by Kronecker et al.
> 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.
Moreover, the outcome of this experiment isn't undecidable unless you
allow it to
run for an unlimited time and have a computer with unlimited memory -
which
won't fit within our cosmic horizon. I've added text clarifying this.
> 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!
Exactly. But these constants aren't necessarily negligible.
Chaitin expressed his frustration with this when we met.
If I ask you to list the 10^9 simplest mathematical structures, these
constants
make a huge difference, and I'm worried that if we compute the
probability of
something being 1/3 with one system, we may get
a noticeably different answer with a different system because the
measure changes.
> 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.
These are indeed interesting points. However, I worry that even which
description is simplest may sometimes
depend on those above-mentioned annoying constants.
> 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...)
Again, I think you and I are using the term "mathematical structure"
in different ways.
> 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
Once again, many thanks!
Cheers,
Max
;-)
--------------------------------------
Prof. Max Tegmark
Dept. of Physics, MIT
70 Vassar Street Rm. 37-626B
Cambridge, MA 02139
--~--~---------~--~----~------------~-------~--~----~
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 Mon Oct 08 2007 - 23:02:21 PDT