FOM: Chaitin and mathematical practice

[Don Fallis]

Hi,

Setting aside the difficulties of coding things, I also think that Chaitin's
"K(m) > c" result is very cool and a very intuitive way of proving incompleteness.
 However, I have never been able to fathom the claims that the "K(m) > c"
result (or the Omega number) have serious implications for mathematical
practice.

It has become popular in recent years to argue that mathematicians should
make significant changes in the way that they do business (e.g., by accepting
a bunch of new axioms or, more radically, by using non-deductive methods
of proof.).  First, it has been argued (on philosophical grounds) that they
will suffer no epistemic loss by making these changes.  And, second, it
has been argued that there is a significant mathematical gain to be had
by making these changes.

Many discussions of Chaitin's work seem to fall under this second category.
 However, as far as I can see, the only really compelling arguments (in
this category) do the following:  They show that there is something that
*we would want to be able to prove* (or disprove), but that is impossible
(or computationally infeasible) to prove given our existing techniques.
 (For example, a proof of the undecidability of CH is an argument of this
sort.)  It is not clear that Chaitin has done anything like this.     

take care,
don

PS. Here are some other articles that claim that the implications of Chaitin's
result are somewhat overstated:

TI: ALGORITHMIC INFORMATION THEORY.
AU: VAN-LAMBALGEN,-MICHIEL
SO: Journal-of-Symbolic-Logic. 1989; 54,1389-1400.

TI: The Source of Chaitin's Incorrectness
AU: Fallis,-Don
SO: Philosophia-Mathematica. 1996; 4(3), 261-269.

PPS. I believe that Boolos once gave a talk where he claimed that Chaitin's
incompleteness result was a riff on the Berry paradox (i.e., "the least
integer that cannot be named in fewer than thirteen words") in the same
way that Goedel's incompleteness result is a riff on Russell's paradox.
 Does this sound familiar?  Was it ever published? 


Don Fallis
Assistant Professor
School of Information Resources and Library Science
University of Arizona
1515 East First Street
Tucson, AZ 85719