Re: Raatikainen's critique of Chaitin

From: KRamsay (kramsay_at_aol.com)
Date: 09/08/04 

Date: 08 Sep 2004 20:05:10 GMT

In article <b671fc3e.0409071910.541378bd@posting.google.com>, cafeinst@msn.com
(Craig Feinstein) writes:
|I can only quote what he said in the book "The Limits of Mathematics".
|I don't know who was first to exhibit a bi-immune set, but it appears
|that Chaitin believes that he was:
|
|"How does this differ from what I do? I use an exponential diophantine
|equation, which means I allow variables in the exponent. Matijasevic
|only allows constant exponents. The big difference is that Hilbert
|asked for an algorithm to decide if a diophantine equation has a
|solution. The question I have to ask to get randomness in elementary
|number theory, in the arithmetic of the natural numbers, is slightly
|more sophisticated. Instead of asking whether there is a solution, I
|ask whether there are a finite or infinite number of solutions---a
|more abstract question. This difference is necessary.
|
|My two-hundred page equation is constructed so that it has a finite or
|infinite number of solutions depending on whether a particular bit of
|the halting probability is a 0 or a 1. As you vary the parameter, you
|get each individual bit of ©. Matijasevic's equation is
|constructed so that it has a solution if and only if a particular
|program ever halts. As you vary the parameter, you get each individual
|computer program."

I don't see him claiming specifically that this property of each
correct algorithm only solving finitely many cases of the problem
(i.e. bi-immunity) being original with him. I don't know who got
such a result first, but it just seems unlikely that his was first.
Post had a "one-sided" immunity result in 1944. In 1968 Jockusch
had a paper in the Journal of Symbolic Logic volume 33 titled
"The degrees of bi-immune sets", which I doubt he would have written
if they didn't know there were any. If one does a Google[tm] search
for "bi-immune", one gets swamped with more recent references to
bi-immunity for resource-bounded complexity classes.

I can't promise that immunity was introduced in 1944, and bi-immunity
not until the mid 1960s, but it seems unlikely to me.

I've always found it hard to tell from these papers exactly how
much is supposed to be original. He does seem willing in his academic
papers to give due credit and include references to prior work (as
is normal). But if you really want to get a good idea of how original
it is, you need something more than knowing that theorem 3.4 was first
discovered by the author. One needs some knowledge of what the state
of the art at the time was.

My guess would be, like with most famous results, that it's original
but not shockingly so. I don't think our problem is with the idea
that he had new results, but with the idea that they're revolutionary
new results.

In article <b671fc3e.0409080804.7b9be414@posting.google.com>,
cafeinst@msn.com (Craig Feinstein) writes:
|The fact that he used an exponential diophantine equation instead of a
|diophantine equation does not make the basic principle that it is
|impossible to know whether there are infinitely or finitely many
|solutions weaker than Matiyasevich et al's results. The type of
|equation is irrelevant.

So all that effort by Matiyasevich, Robinson, and others to arrange
for it to be a polynomial equation and not just a formula in terms
of primitive recursive functions was useless, eh? You learn something
new every day.

|> I would say that all in all, you are doing Chaitin no favors by
|> trying to support him the way you are doing. It would be sort of
|> like if the peanut gallery at a symphony were to start chanting in
|> favor of their favorite violin being made first chair. Imagine
|> laypeople lobbying for Andrew Wiles to be honored as "world's
|> greatest mathematician". I'm sure it's flattering to have a fan
|> base, but really I think it does more to cloud the issue of how
|> to evaluate his contribution to the subject than to clear it up.
|> It's possible to ruin a perfectly good reputation by trying to
|> elevate it too high, or by trying to base it too narrowly on some
|> single famous result.
|
|You are just jealous of Chaitin.

There are so many people out there who have succeeded far beyond
what I have, that it would be very silly of me to single out this
one guy to try to tear him down. If there's anybody I'd be tempted
to take a poke at, it would be one of these guys who got granted
tenure and then proceeded to do no research at all.

Or somewhere at the opposite end of the spectrum, why not be much
more envious of a guy like Shelah? It seems like nearly every time
I go to the library to look at recent journals, he's got papers in
some of them. If I had to weigh stability theory against algorithmic
information theory as far as overall value to the future of the
subject, I'd be very wary of underestimating stability theory.
Certainly Shelah's raw theorem-proving ability is more impressive.

|By the way, I'm not writing all of
|this to support him, as I've never met him. I did talk to Chaitin
|through email though, and he knows that I started this thread. I
|started this thread, because I don't like falsehood and Raatikainen's
|critique of Chaitin is based on falsehood.

I'm sure you mean well, but so do I. I don't like false announcements
of big paradigm shifts. I think it would be better for all concerned
if such claims were put to rest. I don't mind if authors sometimes
get excited by what they're talking about. (I saw a paper about the
Robertson-Seymour theorem that wrote "Wow!") :-) But let's also have
a little sober estimation of the situation. Revolutions in mathematics
are rare. It doesn't poo-poo anybody's contribution to say that it
doesn't quite constitute a revolution, with all due respect.

|If he is representative of
|AMS where he made the review, then the AMS is not worth much.

I think it's silly to take an author of a review published in a
journal published by the AMS as a "representative" of the AMS.

The worth of the AMS is not as a kind of cadre of elite opinion
setters, but as a "big tent" where mathematicians can come together
to encourage the advancement of mathematics. People sometimes say
dumb things in letters to the AMS or in reviews, but that's just
life. In this case, however, I wouldn't even call the review bad.

|No one
|who has posted here has said anything to refute this.

I don't want for you to rehash the whole thread, but I never did see
a convincing explanation of what Raatikainen wrote that was actually
false. I've read an awful lot of this discussion that has been purely
about relatively ill-defined notions such as whether certain
mathematical facts are "true for a reason", whether an axiom n=n
where n is computationally complex is very "informative", and so on.

It seems to me that Raatikainen's main object is to steer people away
from naive interpretations of such statements of Chaitin's as

   In such an approach it is possible to argue that if a theorem
   contains more information than a given set of axioms then it is
   impossible for the theorem to be derived from the axioms.

One has to use very carefully selected (even a little contrived)
versions of the informal notion of "contains information" to make
this come out right.

Keith Ramsay

Relevant Pages

  • American Mathematical Society 2008 Awards
    ... American Mathematical Society 2008 Awards ... The American Mathematical Society (AMS) is presenting several prizes at the Joint Mathematics Meetings in San Diego on January 7, 2008, including two prizes that are awarded jointly with two other mathematics organizations, the Mathematical Association of America and the Society for Industrial and Applied Mathematics. ... AMS Leroy P. Steele Prize for Lifetime Achievement: GEORGE LUSZTIG of the Massachusetts Institute of Technology, for entirely reshaping representation theory, and in the process changing much of mathematics. ...
    (sci.fractals)
  • Some references on the new historical event
    ... of the Hamilton-Perelman theory of Ricci flow. ... The Geometry and Topology of Three-Manifolds ... See also the Notices of the AMS, Volume 52, Number 4, ... AMS 2000 Mathematics subject classification ...
    (sci.math.research)
  • Re: THE ERROR OF EINSTEIN /RIEMANN C^2-1
    ... WE WILL BRING THE COMEDY SHOW OF MATHEMATICS TO AN END VERY SOON, Giving the AMS a chance to concede to 19 by two weeks. ...
    (sci.math)