FOM: Chaitin and Incompleteness

[Raatikainen Panu A K]

First, let me note that it seems there has been some 
misunderstandings between me and Shipman which became 
apparent in his last posting - it is obvious that on various issues, 
we've been talking on different issues. 

But still, I have some comments


On 26 Mar 01, at 11:14, Joe Shipman wrote:

> Raatikainen:
> >RE: I am sorry to disagree: I submit that it makes no sense to talk
> >about programming the syntax - in the context of Turing machines
> >reading and writing only zeros and ones, which is the case in the
> >algorithmic information theory - independently of a binary coding
> >of the syntax.
> 
> I think we differ about the meaning of "arithmetize".  I am not
> requiring the Turing machines to have a binary alphabet, and I am
> certainly not requiring that they be formalized in a theory of
> arithmetic with only + and * as operations.  ZF, or ZF-Infinity, can
> *formalize* Turing machines perfectly straightforwardly, and the
> Turing-machine-coding needed to make a Universal Turing Machine and get
> results about the Halting Problem is MUCH easier than "arithmetizing
> TM's" in the sense of representing them in Peano Arithmetic.

RE: Yes, I took it for granted that we focus on Turing machines 
with binary alphabet. But it seems to me that this is needed for 
various key definitions and results in Algorithmic Information 
Theory. A possible more genralized approach would be interesting 
but is non-standard. 

I must admit that I don't recall that I have ever seen the theory of 
Turing machines developed in Set Theory (do you have any good 
references?) - it is interesting to hear that it makes UTM etc. much 
easier (by the way, there is an unpublished textbook manuscript by 
M. Fitting where he developes the Gödelian approach in Set Theory 
- also it turns out to be somewhat simpler in that context ...)

But I still wonder whether one need not to somehow code Turing 
Machines to sets before one can formalize them in Set Theory ?


* * *

One final clarification: the approach  to the incompleteness results 
via Turing Machines has certain appeal - I do not intend to deny 
this. But wouldn't it then be better to credit Turing (rather than 
Chaitin) - for the proof of the first incompleteness theorem by using 
the Halting Problem was given already by Turing himself in 1936...


All the best

Panu Raatikainen