[FOM] inconsistency of P

Panu Raatikainen panu.raatikainen at helsinki.fi
Sat Oct 1 00:32:47 EDT 2011

Tao wrote:

> Basically, in order for Chaitin's theorem (10) to hold, the  
> Kolmogorov complexity of the consistent theory T has to be less than  
> l.

Nelson wrote:

> So far as I know, the concept of the "Kolmogorov complexity of a  
> theory", as opposed to the Kolmogorov complexity of a number, is  
> undefined.

Diamondstone wrote:

> You can talk about the Kolmogorov complexity of anything that can be  
> coded with a number, including any finitely axiomatizable theory  
> (code the axioms with a number) or any computably axiomatizable  
> theory (code the machine enumerating the axioms with a number).

Ihis is true - but it does not make sense to talk about *the*  
Kolmogorov complexity of a theory, as this is totally relative to the  
particular way of arithmetization, and the choice is arbitrary. You  
can make the complexity of a theory T arbitrarily small, or large,  
with different choices.

In particular, Tao's claim quoted above is false.

Read my:




Panu Raatikainen

Ph.D., University Lecturer
Docent in Theoretical Philosophy

Theoretical Philosophy
Department of Philosophy, History, Culture and Art Studies
P.O. Box 24  (Unioninkatu 38 A)
FIN-00014 University of Helsinki

E-mail: panu.raatikainen at helsinki.fi


More information about the FOM mailing list