From: Lee Corbin (lcorbin@ricochet.net)
Date: Mon Apr 02 2001 - 18:18:51 MDT
Greg Burch forwarded the very nice article on Chaitin's Omega
on Sun Apr 1, 2001, 9:31 am.
> Chaitin formulated a Diophantine equation that was 200 pages
> long and had 17,000 variables. Given an equation like this,
> mathematicians would normally search for its solutions.
Yeah, right. I can just see them sitting down to work on it.
(I presume that their whiteboards aren't big enough. :-)
But maybe I'm just projecting my own feelings of inadequacy and
incompetence: I can't solve either of the simple Diophantine
equations "ab - cd = 1" or "a^2 + b^2 = c^2 + 1". I worry
that the first may not even be possible---that is, are there
four functions a=a(n,m,...), b=b(n,m,...), c=c(n,m,...),
d=d(n,m,...) that yield all the pairs of factors whose
difference is 1? (If you know the solution to either
of these, please, let me know!)
Samantha the Skeptic wrote
> On the face of it I would be surprised if you could rigorously
> show the existence of such a (Chaitin's Omega) beast without
> making it somewhat calculable. It looks like a philosophical
> thought experiment run amok.
As I understand it, it's pretty easy to see that it exists
(especially if you are a mathematical Platonist). The nth
bit of Omega is precisely whether the nth Turing machine
halts (given any concrete scheme at all for enumerating
Turing machines). It's clearly not calculable since you
can't know for many bits whether they are one or zero.
> Actually, no Godel didn't do any such thing ("blew a
> gaping hope in mathematics") or at least not with what
> are popularly thought to be the implications
The formalists were pretty upset; and, although I don't
really like the metaphor, the image that does come to
mind that fits the metaphor is The List of All True Math
Relationships (listed in the appendix of God's Book,
according to Paul Eotvos--- 'scuse the spelling, it's
pronounced Ehrdish).... anyway, The List has lots of
Relationships that can't properly be called Theorems
because they don't have proofs. Each such unprovable
theorem WOULD indeed look like a gaping hole to a
formalist.
> OK, so you can build a mapping. But it is another
> thing to say that mapping implies things true in one
> domain are true in the other without more evidence
> than just such a mapping.
I'm sure that they prove iso- or homo- or something-
morphism. But I agree with you that some of the
claims in the science article were hyped, and thanks
for reminding people like me to approach even things
others know a lot better with a bit of skepticism.
And Eliezer Yudkowsky wrote
> Except for the idea that the Goldbach Conjecture
> (NOT the Riemann Hypothesis, as stated in the article)
> might be true but TOTALLY unproveable (i.e., the
> consequence of an infinite number of independent
> mathematical facts). I've heard this hypothesized
> before in connection with Chaitin's work, and I find it
> both plausible and chilling.
Well, no more than Godel's Theorem is chilling. Right?
But what's the difference between the GC and the RH that
you allude to? Mightn't it be true, i.e., actually
the case, that either one is true but unprovable?
Here is a puzzle that I formulated on this subject that's fun.
A great mathematician is at a party, and two students come
up to him. One says, "I have found a proof that Goldbach's
Conjecture is unprovable!". The mathematician snorts, "Go
away, you crackpot". Then the other student says, "I have
found a proof that whether or not there exist infinitely
many prime pairs is unprovable!", and the mathematician's
eyes light up and he says "Oh, really!? Please tell me
more!". Why was the mathematician eager to hear out the
second student, but not the first?
Lee Corbin
This archive was generated by hypermail 2.1.5 : Sat Nov 02 2002 - 08:06:48 MST