**Next message:**Spike Jones: "Re: MATH/COMP/PHIL: "Omega Man""**Previous message:**Damien Broderick: "Re: "analog computer" = useless hypothesis?"**In reply to:**Lee Corbin: "Re: MATH/COMP/PHIL: "Omega Man""**Next in thread:**Spike Jones: "Re: MATH/COMP/PHIL: "Omega Man""**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

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

**Next message:**Spike Jones: "Re: MATH/COMP/PHIL: "Omega Man""**Previous message:**Damien Broderick: "Re: "analog computer" = useless hypothesis?"**In reply to:**Lee Corbin: "Re: MATH/COMP/PHIL: "Omega Man""**Next in thread:**Spike Jones: "Re: MATH/COMP/PHIL: "Omega Man""**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ]

*
This archive was generated by hypermail 2b30
: Mon May 28 2001 - 09:59:44 MDT
*