Re: Raatikainen's Complexity Complex

From: Eray Ozkural exa (erayo_at_bilkent.edu.tr)
Date: 08/29/04 

Date: 29 Aug 2004 03:15:18 -0700

"Paul E. Black" <p.black@acm.org> wrote in message news:<pan.2004.08.26.17.14.56.581126@acm.org>...
> On Thu, 01 Jul 2004 06:48:03 -0700, Eray Ozkural exa wrote:
>
> > the following quote in Raatikainen's much philosophical JPL article
> > that is entirely misled: [*]
> >
> > Raatikainen (jpl): As a ridiculously simple example, take as a theory
> > F1 some very large and (with respect to given coding) enormously
> > complex finite set of equations of the form n=n. Now according to the
> > received interpretation, this theory is extremely powerful or
> > informative. But of course, it is in fact very weak and quite useless.
> > It is contained in the very simple and trivial theory F2 that consist
> > of the single axiom (forall x)(x=x)
> >
> ...
> >
> > First, Raatikainen thinks that "n=n" has a fixed meaning, given by an
> > outside observer. [!] More terribly, he thinks an axiom string that
> > contains "n=n" k times:
> >
> > n=n --
> > n=n |
> > ... | k times (A1)
> > n=n --
> >
> > has *identical* information content to an axiom string that solely
> > consists of "n=n" (A2).
> >
> > In addition, he thinks that the axiom string A1 is "enormously
> > complex", while in reality it has information content H(k) + H("n=n")
> > + c = H(k) + O(1) (one can take k as the binary representation for
> > natural number k here). It does not automatically become enormously
> > complex, if you take k to be a (small!) number such as 10^6, which
> > consists of only a few digits. To make A1 enormously complex, one
> > would indeed have to pick an enormously large and *complex* number.
>
> One reading of Raatikainen's theory F1 ("equations of the form n=n")
> is something like the following:
>
> 1=1
> 12=12
> 2547=2547
> 7439264832984392145639471389643257=7439264832984392145639471389643257
> etc.
>
> If it is a haphazard ("random") collection of such axioms, it would be
> hard to express very compactly. Thus I believe the Kolmogorov
> complexity of the theory would be quite high.
>
> I cannot say what effect this interpretation has on the rest of his
> argument.

OK. First F1 was not exactly like that in Raatikainen's paper, the
form is k conjunctions of the form x_i=x_i. Raatikainen's (brilliant!)
insight is that the *logical semantics* of this sentence is subsumed
by "forall x (x=x)", while the K("forall x (x=x)") < K(A1), where A1
stands for the axiom schema of F1.

What effect this interpretation has on the rest of his argument? I
have presented at least three major flaws in Raatikainen's paper, all
of them logical.

Let me focus on one of these flaws as a reply to your question.
Indeed, A1 can have high complexity. That depends on how we choose
x_i.

The mistake of Raatikainen goes like this. Raatikainen fixes as the
inference rules, some kind of (completely vague!) logical inference
engine. This inference engine cannot "read inside" x_i, it treats them
as blocks. So if you had an axiom sentence like "3=3 & 10=10" you
could not infer anything else than the trivial facts that 3 is 3 and
10 is 10.

However, in Chaitin's formalization of an axiomatic theory (this part
is vital!), the situation is vastly different because there is no
restriction on how we fix the inference rules. In principle, this
means that you can put any algorithm there which can "interpret" the
axioms any way it likes. [*]

This means that, large parts of mathematics can be encoded in the x_i
for A1 with sufficiently high complexity, for instance number theory,
calculus, geometry, topology and probability theory. Obviously, such
complex axiom schema cannot be present in "forall (x=x)", which shows
Raatikainen's mistake (which is a mix of bad philosophical and
mathematical assumptions)

An additional remark: it is obvious that some short nonhalting
programs can generate strings that contain substrings with higher
program-size complexity, that is handled by extensions of Kolmogorov
theory (see for instance Schmidhuber's work). Raatikainen's work does
not even come close to revealing this interesting but simple property
of Kolmogorov complexity.

Regards, 

--
Eray Ozkural
[*] For instance, it could be the mind of Kolmogorov, and the axiom
string could state, in natural language terms, an axiomatic
description of Kolmogorov complexity. (assuming of course minds are
computers, this is just an example)

Relevant Pages

  • Re: Raatikainens Complexity Complex
    ... Thus I believe the Kolmogorov ... > I cannot say what effect this interpretation has on the rest of his ... stands for the axiom schema of F1. ... A1 can have high complexity. ...
    (sci.math)
  • Re: Predicting the Future and Kolmogorov Complexity
    ... portion of a sequence or pattern based on what was already known. ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ...
    (talk.origins)
  • Re: For Sean Pitman: Review of "Meaningful Information"
    ... portion of a sequence or pattern based on what was already known. ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ...
    (talk.origins)
  • Re: For Sean Pitman: Review of "Meaningful Information"
    ... portion of a sequence or pattern based on what was already known. ... complexity" as defined and modified by those like Kolmogorov, Chaitin, ... The algorithm used to compute pi doesn't ...
    (talk.origins)
  • Re: a complexity measure for subsets of R
    ... The goal is to define a "complexity measure", ...    A' and B' are disjoint and measurable, ... c is translation invariant -- that is, ... Axiom should be retained. ...
    (sci.math)