FOM: Re: Chaitin

[Raatikainen Panu A K]

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