Re: Raatikainen's critique of Chaitin

From: Craig Feinstein (cafeinst_at_msn.com)
Date: 09/06/04 

Date: 6 Sep 2004 09:16:50 -0700

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

Craig