FOM: Re: Chaitin

[Harvey Friedman]

Reply to Raatikainen 3/21/01 12:08PM:

The main issue that Chaitin's work does not address is this:

is there any reason to consider extending the usual axioms for mathematics
(ZFC)?

Chaitin's work says, in various interesting ways, that there are certain
things that would be nice to do that cannot be done in any reasonable
formal system whatsoever.

But this cannot be a reason to extend the current axioms, because the
problem will arise in the same way for any extension.

Also, Chaitin does not give us a specific task that we cannot accomplish in
our present formal systems, or any reasonable formal system. In fact,
Chaitin does give us an infinite list of tasks that we cannot accomplish
all within any formal system. However, this is not all that surprising
since formal systems are finitary. His example is "determine each digit of
the halting probability Omega". However, this formulation of his result is
presumably easier than his full result, as it depends only on the
nonrecursivity of Omega.

Chaitin does give us an infinite list of tasks, and shows that we cannot
accomplish infinitely many of these tasks within ZFC, or even within any
reasonable formal system. Again, the tasks are determining the digits of
the halting probability Omega.

Of course, the original Godel work does give us a specific task that we
cannot accomplish in our present formal systems, and which, historically,
was sought after and believed to be obtainable, and has the highest
significance - consistency.

It is true that the interesting tasks that Chaitin tells us we cannot hope
to accomplish in various senses are of this character:

*they are not at all like the kinds of things that mathematicians try to
do, or even conceive of trying to do; in fact, it is intrinsically
different than those kinds of things*

This is partly because of the nonrobustness of the underlying notions used.
The mathematical interest of detailed quantitative information about
structures generally depend on their robustness.

This is presumably why Chaitin sometimes works with exponential Diophantine
equations. But these are still rather disgusting mathematically. One cannot
hope to use ordinary Diophantine equations because of the lack of knowledge
about them, so that one does not get presentable quantitative information.

>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

I think that more is true:

For every consistent reasonable formal system F, there is a finite constant
c such that F cannot prove any sentence of the form K(n) > c.

Under a standard presentation of K, roughly how big does c need to be for
ZFC? And what effect is there if we use PA (Peano Arithmetic) instead of
ZFC?

>b) Chaitin 1986 (mentioned by Jeff Ketland)
>	Any formal system F can determine only finitely many digits of
>	the halting probability Omega.

Again, under a standard presentation of Omega (i.e., a standard setup for
Turing machines), roughly how many digits can be determined in ZFC? And
what effect is there if we use PA (Peano Arithmetic) instead of ZFC?

>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.

But what if we fix the presentation of Turing machines to be reasonably
natural, in advance, and then change the theories?

As a simplified example, suppose we are interested in the size of the
smallest Turing machine TM which does not halt but cannot be proved to not
halt in PA or ZFC. How do these sizes compare?