FOM: Chaitin and Incompleteness
Raatikainen Panu A K
Praatikainen at elo.helsinki.fi
Tue Mar 27 04:17:27 EST 2001
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:
> >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
More information about the FOM