Re: Panu Raatikainen's review of two of Chaitin's books.

From: Aatu Koskensilta (aatu.koskensilta_at_xortec.fi)
Date: 05/14/04

  • Next message: Eray Ozkural exa: "Re: Panu Raatikainen's review of two of Chaitin's books." 
    Date: Fri, 14 May 2004 14:59:39 +0300

    Ralph Hartley wrote:

    > Aatu Koskensilta wrote:
    >
    >> Now, assume G is a Turing machine, s.t. G does not halt on empty input
    >> but T does not prove this, and furthermore, T does not prove any
    >> sentence of form "if G would halt, it would output k" where k is some
    >> number. More formally we can express these conditions as follows
    >>
    >> 1) G(0) undefined, but not T |- G(0) undefined 2) for all k, not T |-
    >> G(0) defined --> G(0) = k
    >>
    >> Let c be the index of G.
    >
    >
    > Of course there are many such Gs with many indexes.
    >
    > What you meant to say is "Let c be the *least* index of such a G."

    Yes, that is indeed what I meant to say.

    >> Of course, it can now be objected that the indexing we have chosen to
    >> show that the characteristic constant of PA = characteristic constant of
    >> ZFC is entirely unnatural. This is of course true,
    >
    >
    > But irrelevant.
    >
    > The whole reason it is OK to just look at TMs and ignore all other
    > models of computation is that they are equivalent. If you pay attention
    > to the fact that one indexing is "more natural" than another, then you
    > have to argue the merits of different models, since the description of
    > one in terms of another is often very "unnatural."

    Right. Any acceptable indexing can be thought of as a "programming
    language", and the function sending these indices to standard ones (in
    terms of TMs) as a "compiler". One would think that the natural place to
    look for naturalness is this function sending indices to codes of Turing
    machines.

    I don't know if there has been any work in the direction of finding a
    suitable definition of "natural". There are some properties which seem
    prima facie natural, e.g. given two indices a and b of two algorithms
    f(x) and g(x), the index - whatever the determinate article means here -
    of f(g(x)) should not be of order A(a,b) or greater, where A is the
    Ackermann function, and similarly for some other basic operations.
    Perhaps we should require that the indexing is not only acceptable, but
    that the recursive function that translates between this indexing and
    the "standard" one be feasible in some sense.

    However interesting these sort of ideas might be, they're not relevant
    to Raatikainen's analysis of Chaitin's claims. This is because although
    feasibility of the "compiler" function might be relevant to many things
    including real world applications and philosophical musings about
    epistemological value of simplicity, it's not a sensible requirement to
    place on a "programming language" (i.e. a system of indices) intended
    only to define and describe sequences of bits (or more complicated
    structures coded as such), not to actually produce them. I see no reason
    to expect all possible schemes one might invent for this purpose to be
    even primitive recursively related to Turing machines, although perhaps
    as an empirical fact they are - ruling out schemes defined only to
    refute this.

    So Chaitin is wrong and Raatikainen's criticism of his grandiose claims
    is entirely justified. 

    -- 
Aatu Koskensilta (aatu.koskensilta@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
  - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
  • Next message: Eray Ozkural exa: "Re: Panu Raatikainen's review of two of Chaitin's books."

    Relevant Pages