Re: Raatikainen's critique of Chaitin

From: KRamsay (kramsay_at_aol.com)
Date: 09/07/04 

Date: 07 Sep 2004 16:16:43 GMT

In article <b671fc3e.0409060816.3405bbb8@posting.google.com>,
cafeinst@msn.com (Craig Feinstein) writes:
|"3.14159" <pi@the.sky> wrote in message
|news:<BiQ_c.3570$Nd6.141784@news20.bellglobal.com>...
|> Craig Feinstein wrote:
|>
|> >Robin Chapman <rjc@ivorynospamtower.freeserve.co.uk> wrote in message
|news:<chffjd$ba$1@news8.svr.pol.co.uk>...
|> >
|> >>>Chaitin's Theorem (about Omega, which is really his big result) shows
|> >>>that only a finite number of bits of Omega are possible to determine;
|> >>>the only way to determine more bits is to call them axioms. Since the
|> >>>bits can be represented as exponential diophantine equations (1 if
|> >>>there are infinitely many solutions, 0 if only finitely many
|> >>>solutions), we see that there are some statements in number theory
|> >>>that are unknowable.
|> >>>
|> >>>
|> >>Already proved by Matiyasevich et al.
|> >>
|> >>
|> >No, you missed the point. I'm surprised that you would post on a
|> >subject matter that you obviously don't understand. Matiyasevich's
|> >result was when we are to determine whether an equation has a solution
|> >or not. Chaitin's result is whether there are infinitely many
|> >solutions or not. There is a big difference, in fact the key which
|> >makes Chaitin's result stronger. Think about it or read Chaitin's
|> >work.
|> >[ snip ]
|> >
|> >
|>
|> For every Diophantine equation E1 there constructively exists
|> a Diophantine equation E2 such that E2 has infinitely many solutions
|> if and only if E1 has a solution.
|>
|> The proof is an easy exercise. Just add another unknown.
|>
|> See M. Davis, Proc. AMS 35 (1972), 552-554, for this and other less
|> obvious reductions.
|
|Again, this misses the point. Your statement may be true but is
|irrelevant in the context of this discussion. You cannot also say that
|for every Diophantine equation E2, there constructively exists a
|Diophantine equation E1 such that E1 has a solution iff E2 has
|infinitely many solutions. Because of this fact, Chaitin's result is
|much stronger.

Choosing a richer class of problems doesn't strengthen the result,
it weakens it!

For example, dealing with exponential Diophantine equations was
a weakening of the result (which Chaitin wrote didn't concern him--
he preferred making it simpler to crank out a concrete instance of
such an equation to adhering to the exact restriction of the formula's
being a polynomial).

The fact that each algorithm that correctly solves some subset of
the problems, only solves a finite subset of the problems, is known
as recursively enumerable bi-immunity. We can encode the problems
with natural numbers, so that the problem becomes a subset of N.
A subset S of N is bi-immune for a class C if S is infinite but does
not contain an infinite subset in C, and N-S is also infinite and also
does not contain an infinite subset in C.

You couldn't have a bi-immunity result for the problem of whether
a Diophantine equation has one solution, because that's (infinite
and) recursively enumerable itself. We have, at a minimum, the naive
algorithm that goes hunting for a solution and tells us that there
is one if it find it. So in order to prove a bi-immunity result, he
did have to work with an enlarged class of problems. But doing so
doesn't itself strengthen the result.

Bi-immunity was a concept from the early years of recursion theory,
and wasn't a novelty introduced by Chaitin. I don't happen to know
who first exhibited a bi-immune set, but I'm sure it was well before
Chaitin.

Once Matiyasevich et al had their result, results about recursively
enumerable sets automatically became results about sets of
solutions of diophantine equations. So dealing in (exponential)
Diophantine equations is not what was novel here either.

The "bi-immunity" of the 1 bits of Omega has a nice kind of
uniformity to it, in the sense that not only are the recursive
subsets of it (and its complement) finite, but their size is bounded
in terms of the size of the program doing the enumerating. I don't
know whether this result had any precursors in the literature, but
logicians had already gone quite far in developing the techniques
needed to do it.

In this case, for example, if I imagine not knowing anything about
randomness, and I suppose I want to exhibit a binary sequence r that is
"strongly" immune for a sequence of machines, it goes something like
this. Suppose that we have an enumeration of Turing machines T_1, T_2,
... that compute partial recursive functions I'll also call T_1, T_2,
.... At first I suppose that I have some function f(N), which I'll try
to make slow-growing, and also try to prevent any machine T_m where m
is an N-bit number (i.e. 2^N<m<=2^{N+1}) from generating >f(N) bits
of my number r correctly, without also generating some other bits
incorrectly. So for each machine T_m that generates too many bits, I
want to prevent my real r from agreeing with all of them. That means
r has to avoid the set S_m consisting of all reals whose k-th bits are
T_m(k) whenever T_m(k) is defined.

The worst-case scenario here is that each machine T_m generates
exactly f(ceil(log_2 m))+1 bits. The measure of the set S_m is then
2^{-f(ceil(log_2 m))-1}. It occurs to me that by a simple measure-theory
argument, I can arrange for r to avoid all of these sets as long as
the sum of their measures is <1. The sum of the measures is <= the sum
over N of 2^N * 2^{-f(N)-1}. To get this to converge to something less
than 1, I need for f(N)-N to grow something a little faster than
log_2(N)... f(N)=N+C+2*log_2(N) will do....

But then I remember a remark of Chaitin's I read, about his care with
log terms. He remarks on his having chosen Lisp as the language for
his algorithms partly so they would be "self-terminating": no program
is a prefix for another program. If you are read a valid program, when
the last symbol is read to you, you know it's done without having to
be told that that is the end of the program. This can account for
roughly a logarithm term; if I encode machine number m using g(m) bits,
and avoid any machine being a prefix of another machine, the function
g(m) has to satisfy sum_m 2^{-g(m)} <= 1, which is essentially the
inequality I needed in my argument.

So if the machines are being represented in self-terminating form,
I can just let f(N)=N. No extra constant term is required. The total
measure of the S_m is then <= 1/2. Any real in [0,1] that isn't in
the union of these S_m satisfies this very strong immunity from any
of the machines correctly matching more bits of it than were used to
represent the machine.

Note several things about the argument. First, I didn't really use
the fact that the machines were Turing machines. They could be any
kind of oracle machines or whatever. The fact that I've proven it in
a Turing machine setting is a red herring. Second, it's almost a
mindless argument. I'm not any kind of recursion theorist; a recursion
theorist worth his salt can easily cook up arguments of this kind. The
literature is full of far more sophisticated arguments. This one is
sort of what occurs to a person after they've browsed through a few
diagonal or finite injury arguments. Notice it also doesn't use
anything special to algorithmic information theory. It's not the same
as the argument Chaitin uses. I'm not claiming the argument I sketched
is especially pretty, just that it uses nothing other than standard,
tools that were already old when Omega was defined.

If one examines the argument more carefully, one can see that it's
possible to choose the real r to be what they call delta-0-2: if we
think of the real as being a branch on an infinite binary tree, going
to the left for each 0 bit and to the right for each 1 bit, it's a
branch that merely needs to avoid a certain recursively enumerable
set of nodes. We can take r to be the leftmost such branch, which
means one of the bits of r is 1 just in case the left hand side at
that node is (eventually) blocked off. That's kind of statement can
be shown to be effectively convertible into a statement that a certain
recursively enumerable set is finite. (If we let r be the rightmost
branch, then the k-th bit of r being 1 is equivalent to a certain
recursively enumerable set being infinite.) Showing that some simple
collection of statements is "universal" for some standard class is
also one of those things logicians seem to do in their sleep.

My main point here is that we're not dealing with anything all that
different from what logicians had been doing all the time beforehand.
Chaitin's Omega certainly is a cuter example, in that it has a much
more natural interpretation.

I would say that all in all, you are doing Chaitin no favors by
trying to support him the way you are doing. It would be sort of
like if the peanut gallery at a symphony were to start chanting in
favor of their favorite violin being made first chair. Imagine
laypeople lobbying for Andrew Wiles to be honored as "world's
greatest mathematician". I'm sure it's flattering to have a fan
base, but really I think it does more to cloud the issue of how
to evaluate his contribution to the subject than to clear it up.
It's possible to ruin a perfectly good reputation by trying to
elevate it too high, or by trying to base it too narrowly on some
single famous result.

Keith Ramsay

Relevant Pages

  • Re: Halting Problem
    ... computers (infinite time and infinite memory). ... indicating that a program x contains no indefinite loop or recursion. ...
    (comp.programming)
  • Re: StackOverflowException with attribute
    ... I figured that the recursion wasn't infinite. ... it would seem that the call to GetProperties on the ... You need to find some way to break this loop. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Halting Problem
    ... large due to recursion. ... there is a condition for the recursion to terminate. ... they don't have infinite memory. ... All programs without any loop, ...
    (comp.programming)
  • Re: quarry: Infinite loop without using for , while, do-while
    ... int main ... this is a infinite loop, ... It's infinite recursion. ...
    (comp.lang.c)