FOM: Chaitin and Incompleteness

[Joe Shipman]

 Shipman:

 > In defense of Chaitin, I have always found his approach by far the
 > easiest way of establishing incompleteness theorems, and his
 > philosophical insight that the strength of theories is ultimately
 > dependent on their algorithmic information content is important.

 Rattikainen (with my comments in CAPS):

 I strongly disagree. The easiest way is to use the notion of truth and
show by diagonal argument that provable does not exhaust true. (see e.g.
Smullyan's book on incompleteness).

THIS IS NOT SO EASY, EXCEPT FOR SPECIALLY CHOSEN FORMAL SYSTEMS LIKE
SMULLYAN'S WHICH ARE DESIGNED FOR SELF-REFERENCE

Indeed, a rigorous proof of Chaitin's theorem requires one to
arithmetize both Turing machines and the syntax of the theory in
question (Godel's proof requires only the latter) and move back and
forth between these two codings (no wonder so many people have got
lost).

WRONG.  FIRST OF ALL, ONCE YOU HAVE ARITHMETIZED TURING MACHINES YOU
DON'T NEED TO ARITHMETIZE SYNTAX, YOU CAN SIMPLY *PROGRAM* THE SYNTAX.
SECONDLY, YOU DON'T EVEN NEED TO ARITHMETIZE TURING MACHINES TO GET
INCOMPLETENESS RESULTS, JUST TO GET INCOMPLETENESS FOR PEANO ARITHMETIC
WHICH IS MUCH STRONGER.

CHAITIN'S APPROACH VIA THE HALTING PROBLEM MAKES IT VERY EASY TO SHOW
THAT ANY SOUND THEORY WHICH CAN FORMALIZE THE STATEMENTS K(m)>n IS
INCOMPLETE.  ZF OBVIOUSLY SUFFICES, AS DOES ZF + THE NEGATION OF THE
AXIOM OF INFINITY.  THIS LATTER THEORY IS ALMOST TRIVIALLY ISOMORPHIC TO
PEANO ARITHMETIC AUGMENTED BY EXPONENTIATION.  THE ONLY TECHNICALLY
DIFFICULT PART IS IF YOU INSIST ON NOT ALLOWING EXPONENTIATION.  THEN
YOU HAVE SOME HARD CODING TO DO TO PROVE THAT YOU CAN REPRESENT
EXPONENTIATION IN TERMS OF + AND *, AND THAT WORK IS NECESSARY IN any
PROOF OF THE INCOMPLETENESS OF PA.

Further, the claim that "the strength of theories is ultimately
dependent on their algorithmic information content is important" is
simply false, as Shipman's own comments later show when he admits that
"Some very strong theories seem to have much simpler axiomatizations
than much weaker ones".

THAT IS WHY I USED THE WORDS 'ULTIMATELY' AND 'SEEM TO'.  IT IS WRONG TO
INTERPRET CHAITIN'S THEOREM TO MEAN THAT A STRONGER THEORY IS ALWAYS OF
GREATER ALGORITHMIC INFORMATION CONTENT THAN A WEAKER ONE.  THE POINT IS
THAT THE ALGORITHMIC INFORMATION CONTENT GIVES AN UPPER BOUND ON THE
STRENGTH.

-- Joe Shipman