Re: Raatikainen's critique of Chaitin

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

Date: 8 Sep 2004 09:04:28 -0700

kramsay@aol.com (KRamsay) wrote in message
news:<20040907121643.22164.00000618@mb-m05.aol.com>...
> 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!

The fact that he used an exponential diophantine equation instead of a
diophantine equation does not make the basic principle that it is
impossible to know whether there are infinitely or finitely many
solutions weaker than Matiyasevich et al's results. The type of
equation is irrelevant.
>
> 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.

I can only quote what he said in the book "The Limits of Mathematics".
I don't know who was first to exhibit a bi-immune set, but it appears
to me
that Chaitin believes that he was:

"How does this differ from what I do? I use an exponential diophantine
equation, which means I allow variables in the exponent. Matijasevic
only allows constant exponents. The big difference is that Hilbert
asked for an algorithm to decide if a diophantine equation has a
solution. The question I have to ask to get randomness in elementary
number theory, in the arithmetic of the natural numbers, is slightly
more sophisticated. Instead of asking whether there is a solution, I
ask whether there are a finite or infinite number of solutions---a
more abstract question. This difference is necessary.

My two-hundred page equation is constructed so that it has a finite or
infinite number of solutions depending on whether a particular bit of
the halting probability is a 0 or a 1. As you vary the parameter, you
get each individual bit of &#937;. Matijasevic's equation is
constructed so that it has a solution if and only if a particular
program ever halts. As you vary the parameter, you get each individual
computer program."

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

But did they 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.

Again, they may have had the ability to do it, but did they do it?
>
> 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.

You are just jealous of Chaitin. By the way, I'm not writing all of
this to support him, as I've never met him. I did talk to Chaitin
through email though, and he knows that I started this thread. I
started this thread, because I don't like falsehood and Raatikainen's
critique of Chaitin is based on falsehood. If he is representative of
AMS where he made the review, then the AMS is not worth much. No one
who has posted here has said anything to refute this.

Craig

Relevant Pages

  • Re: Raatikainens critique of Chaitin
    ... diophantine equation does not make the basic principle that it is ... dealing with exponential Diophantine equations was ... > as recursively enumerable bi-immunity. ... > not contain an infinite subset in C, and N-S is also infinite and also ...
    (sci.math)
  • Re: Kolmogorov Complexity and physical information
    ... Eray "are there integers with an infinite number of digits?" ... I find it difficult enough to understand Chaitin ... >> without straying into further fields ... ...
    (sci.math)
  • Re: Raatikainens critique of Chaitin
    ... I see that I misread your answer. ... You said that Omega is Chaitin ... and therefore its information content is infinite. ...
    (sci.math)
  • Re: Raatikainens critique of Chaitin
    ... I see that I misread your answer. ... You said that Omega is Chaitin ... and therefore its information content is infinite. ...
    (comp.theory)
Quantcast