A lot of people are saying: "Who cares? This is just Godel's
Incompleteness Theorem again."
Well, yes and no. Godel showed that there were some unprovable
truths. Chaitin is showing that there are some incalculable
equations. But these equations aren't "incalculable" in the sense of
having no answers. These equations are "incalculable" in the sense
that their answers are fully random.
I guess this result is trivial, since a proof is just a certain
kind of calculation, so once you've shown that there are some
unprovables, you've shown that there are some incalculables.
Of course, it's also been shown that there are *important* sentences
which are unprovable in a given axiomatic system, especially the
sentence that says: "This axiomatic system is consistent." We worry
that some claims which we take to be facts might also be unprovable.
(As a side note, Chaitin has nothing new to tell us about the
possibility that the Goldbach Conjecture or the Reimann Hypothesis are
unprovable.)
It's not obvious that Chaitin has demonstrated any important
incalculable problems that Turing didn't already let us know about.
The Halting problem is important and relevant. The question of
whether a computer that runs for an infinite period will generate a
finite output, on the other hand, doesn't seem as relevant to our
lives.
If I were to guess where a theory like this might *really* turn out to
be useful, it's in answering the eternal riddle: P == NP? If Chaitin
could prove that some NP problem had inscrutable structure, like his
Omega problem, then it seems to me that this would be sufficient to
show that NP > P... how could you possibly solve a problem like that
in polynomial time? Of course, the trick then is to actually find an
NP problem that's like that.
If you do this, I *demand* credit in a footnote. :)
-Dan, writing from his new Pentium III
-unless you love someone-
-nothing else makes any sense-
e.e. cummings
This archive was generated by hypermail 2b30 : Mon May 28 2001 - 09:59:44 MDT