Re: Chaitin was: Popper

From: Dan Fabulich (daniel.fabulich@yale.edu)
Date: Mon Sep 11 2000 - 23:07:13 MDT


Hal Finney wrote:

> I think you are talking about
> http://www.cs.auckland.ac.nz/CDMTCS/chaitin/vienna.html?

Yup.

> I felt that Chaitin's larger point was that axioms have a certain
> information content, and they simply can't prove theorems that have a
> larger information content. As he put it, with five pounds of axioms
> you can't prove a ten pound theorem. This suggests that mathematical
> truth may be much more complex than we imagined.

This isn't exactly a new revelation for those who have been paying
careful attention to provability theory. Tarski told us almost
exactly like this.

> Prior to Godel it was suspected that with the right axioms you could prove
> everything that was true. We now know this to be false. Chaitin has
> taken Godel's result and made it quantitative.

It's not as quantitative as he might wish it were. He can't actually
tell you how many pounds of axioms you've got, only that one set of
axioms is formally equivalent to a subset of another stronger set of axioms.

> I'm not sure that this has much relevance outside of mathematics (or
> perhaps meta-mathematics). It challenges the fundamental axiomatic
> approach of mathematics and logic which goes back to the ancient Greeks.
> However Chaitin's suggestion that mathematics should become more of an
> engineering discipline has not been well received. If mathematicians
> had wanted to be engineers they wouldn't have gone into math.

Not engineers, scientists. Any scientist, for example, would have
taken Goldbach's conjecture, Fermat's Theorem, etc. to be law years
ago. It's interesting to see how far we could get taking these
computer experiments to be scientific experiments within the realm of
math.

> We use the phrase "mathematical certainty" as the highest degree
> of assurance possible. Chaitin would challenge that by opening up
> mathematics to areas where no proofs are possible. But math without
> proofs is arguably something different than math.

Science, to be precise. ;) It would be the science of math. One
might expect it to be a very fruitful field of research; we know that
math as it is done today has yielded some important and, surprisingly,
practical results that we can apply in other areas of science and in
engineering. While we would expect the science of math to make more
mistakes than today's mathematicians make, we might also expect them
to reach some of the more interesting conclusions a lot faster than
conventional mathematicians would. For example, if a scientist of
math ran the Goldbach conjecture through a supercomputer and found no
useful counterobjections, and then went on to formulate a few other
interesting experiments based on that conjecture, he might reach some
interesting/practical conclusions in math that would take years if not
centuries for conventional mathematicians to prove.

> Chaitin has some hand-waving about possible connections between Godel's
> results and the uncertainty principle, or between his discovery of the
> essentially random nature of mathematics and the randomness in QM.
> However, the paradoxes of QM take on an entirely different hue when
> considered in light of many-worlds interpretations, where there is
> no randomness.

> Interestingly, Chaitin's theories can take on a different role there;
> Algorithmic Information Theory plays a key part in many-universe models
> that go beyond QM. Wei Dai has a mailing list for exploring the notion
> that all universes exist, and that the "measure" or contribution of
> a universe is proportional to the algorithmic information content of
> that universe, by Chaitin's measure (others have also developed similar
> metrics).

There's an obvious philosophical parallel between microstates and the
truth values of unprovable sentences; it's a fairly natural way of
speaking which mathematicians tend to fall into quite easily.
Remember, for Chaitin, the "bit" is the truth value of an unprovable
sentence; in thermodynamics under MWI, it's finding yourself in one
world as opposed to another.

MWI advocates talk about the other possible worlds as if they really
exist (and, I suspect, they just might). Mathematicians, on the other
hand, talk of spaces or worlds or universes in which Euclid's axioms
hold and spaces/worlds/universes in which they don't, as if these
things actually existed. Chaitin would talk about worlds in which his
equation E given parameters (n[1] ... n[m]) had a finite number of
solutions, and worlds in which E(n[1] ... n[m]) had an infinite number
of solutions.

It's a purely philosophical debate as to whether these mathematical
worlds "actually" exist, whereas MWI has some results that it can
test, but beyond that, the parallel is quite close.

> There is an interesting paradox here; you'd think a universe starting
> with a certain information content could not generate anything which had
> a larger information content (a la Chaitin's results). However, I don't
> think this is true; our own universe may have had almost zero information
> content but it generated us. My explanation is that to single out a
> human being in the multiverse takes a huge amount of information, in the
> form of its "address". The actual rule seems to be that the information
> in a subsystem is limited by the sum of the initial information in the
> universe, plus the information needed to locate and specify the extent
> of the subregion. I wonder what if any connections this might have to
> Chaitin's limitations.

Actually, I interpret Chaitin's results in the opposite way. Just as
entropy tends to increase as time goes on, that is, as you find
yourself in one world after another, so are there MORE formally
undecidable sentences as you start assuming Godel-sentences to be
true. More pounds of axioms have more information content, that is,
more worlds which might turn out to be true given the axioms in
question. Settle one formally undecidable question and even more pop
up; it's an unwinnable game of whack-a-mole.

-Dan

      -unless you love someone-
    -nothing else makes any sense-
           e.e. cummings



This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 15:30:55 MST