FOM: Re: Chaitin
Raatikainen Panu A K
Praatikainen at elo.helsinki.fi
Wed Mar 21 05:08:16 EST 2001
As there are some people here in FOM interested in my critical
work on the interpretation of Chaitin's results, I'll try to explain
shortly my main points.
There are two somewhat different results by Chaitin:
a) Chaitin 1974 (mentioned by Charlie Silver).
For every formal system F, there is a finite constant c such
that F cannot prove any true statement of the form K(n) > c
(even thought there are infinitely many n for which this is true)
- here K(x) is the Kolmogorov complexity of x
b) Chaitin 1986 (mentioned by Jeff Ketland)
Any formal system F can determine only finitely many digits of
the halting probability Omega.
As I have (carefully) formulated them here, above results are just
fine. What is problematic are the ambitious (fantastic?)
philosophical conclusions one has drawn from them.
One has standardly assumed that the size of the limiting constant
c for a theory F (in a) or the number of digits of Omega decided by
F (in b) somehow reflects the power, or content, of F. Sometimes it
is rather said that it is the size, or the complexity, of F which
determines this finite limit.
I show, however, that all this is wrong. Actually, it is determined by
a rather accidental coding of computable functions used. In
particular, there are codings such that theories with highly different
power (say, Q and ZFC) have the same finite limit. Also, the size
and complexity of F are quite irrelevant. For any given finite
collection of formal systems, however different in all respect, one
can always fix a coding such that they all have the same limiting
constant - one can even make it 0.
Futher, the interpretation is seriously confused with use and
mention (e.g. the complexity of a theorem as a syntactical object
(mentioned) vs. the compexity a theorem ascribes to an object
(used)).
For every theory, there is indeed a finite limit, but that is all - the
value of this finite limit does not reflect any natural or interesting
property of F.
All this is argued in detail in my JPL paper - I repeat the essential
argument for the Omega case in my SYNTHESE paper.
Now speaking about Omega, my basic point in the later paper is
rather simple. I attact (besides the above mentioned interpretation)
the claims that this result is "the ultimate undecidability result",
"the strongest possible version of incompleteness theorem" etc.
I point out that Omega is actually Delta-0-2, (and thus even
recursive in Turing's halting set), so it is all too easy to present
undecidability and incompleteless results that are definitively
stronger that Chaitin's. I give some natural examples.
- I am glad to discuss these issues further here in FOM, but I also
recommend my papers for those seriously interested in the issue.
My papers are quite self-contained, and have useful introductions
(and the later paper is even short). I repeat the references:
Panu Raatikainen: "On interpreting Chaitin's incompleteness
theorems", Journal of Philosophical Logic 27 (1998), 569-586.
Panu Raatikainen: "Algorithmic information theory and
undecidability", SYNTHESE 123 (2000), 217-225.
Charlie Silver wrote:
> It seemed to me, despite your assertion at the end of the article
> about the theorem still being of value (or something like that),
> the points you make in the article were devastating. If we take
> away the standard interpretation of the theorem, what do you
> think of value is left?
I am happy to hear that you think that my points were devasting -
that was my intention. On what value is left: well, I was just trying
to be not too devasting and merciless; anyway, I think that the
result (a) shows that there is some difference whether one
constructs an incompleteness result in terms of a simple set rather
than in terms of a creative set, as the standard Goedelian proof
does. But I think that this is the only lasting value that is left.
- Panu
More information about the FOM
mailing list