Re: Raatikainen's Paper on Chaitin
- From: "Stephen Harris" <cyberguard1048-usenet@xxxxxxxxx>
- Date: Thu, 19 May 2005 08:05:58 GMT
"Daryl McCullough" <stevendaryl3016@xxxxxxxxx> wrote in message
news:d6g3ge0mb7@xxxxxxxxxxxxxxxxxx
>I did a cursory read of Panu Raatikainen's paper,
> "On Interpreting Chaitin's Incompleteness Theorem",
> and it seemed, based on first reading, that it is
> on the mark. He repeats the main theorems of Chaitin's
> information-theoretic proof of Goedel's Incompleteness
> Theorem, but then focuses on the question of how meaningful
> is the Chaitin constant of a theory as a measure of the
> power of the theory.
>
> The Chaitin constant C(T) for a theory T (an r.e. theory that is
> strong enough to express arithmetic statements) is defined
> to be the smallest constant c such that T cannot prove that
> there exists an integer n such that K(n) > c.
>
> K(n) is in turn defined to be the smallest index k such
> that Turing machine number k halts on input 0 and outputs
> n.
>
> Raatikainen's main point is that C(T) is greatly dependent
> on the indexing scheme used for Turing machines. In particular,
> Let NH = { Turing machines M such that M does not halt on input 0 }.
> Let PNH = { Turing machines M such that T proves that M is in NH }.
> Let e = the smallest index of any machine in PNH.
>
> The Chaitin constant of a theory T will in many cases
> just be equal to e, with a corresponding Turing machine M_e.
> So the Chaitin constant of a theory is not an intrinsic
> measure of anything about the *theory*, but is (at least
> partially) an artifact of how you have indexed the Turing
> machines.
>
> --
> Daryl McCullough
> Ithaca, NY
>
I think the paper I quote from below further elucidates your remarks.
To me, there is a link between Chaitin's "mistake" and Penrose's "mistake".
www.phil.gu.se/posters/jslic.ps ; By Jorgen Sjogren ; page 10
"Most well-known of earlier attempts to create a measure of the power
of theories use Chaitin's incompleteness theorem, and identities the
power with the information content, designned as the Kolmogorov
complexity, of a theory. Chaitin announced his celebrated incompleteness
theorem in the early 1970's. The theorem states that for every sound,
formal theory S containing elementary arithmetic, there is a constant c,
depending only on S, such that S does not prove any true propositions
of the form K(n) > c.
Here K(n) is the Kolmogorov complexity of the string n, and is a
measure of the difficulty of specifying n. A string has low Kolmogorov
complexity if it has a short description, and a high one if it has no
short descriptions. The notions above can be made precise in different
ways, and depending on how this is done, the theorem and its proof take
different forms. The number c is a natural number and Chaitin and his
adherents interpret this constant as a measure of the information
content of the theory S, and claim that this is an adequate measure of
the power of S. 2 In [Cha82] Chaitin says
that I would like to measure the power of a set of axioms and rules
of inference. I would like to be able to say that if one has ten
pounds of axioms and a twenty-pound theorem, then that theorem
cannot be derived from these axioms.
In the same paper Chaitin says that traditional proofs of Godel's
incompleteness theorem show that formal axiomatic systems are
incomplete, but they do not suggest ways to measure the power of
formal axiomatic systems.
Chaitin's argument runs in two steps. In the first he proves the
incompleteness theorem. In the second step he draws the extra-logical,
or philosophical, conclusion that there is an intimate relationship
between the information content of a formal system, and the constant
in his theorem.
This interpretation, or use, of Chaitin's theorem has been critized by
van Lambalgen [vL89] and Raatikainen [Raa98]. The main goal in this
thesis is to use other means to construct a measure of the power of an
interesting class of extensions of elementary arithmetic. 1 In [Cha82]
Chaitin presents three other possibilities to measure the information
content of a theory, but since we focus on the above mentioned idea, we
will not discuss these other possibilities. 2 See e.g. the introduction
of [Raa98] for some comments on the reception of Chaitin's claims. ...
A brief discusssion of the possibility to draw extra-logical
conclusions from theorems of logic follows, ... to page 11
The structure of the thesis is as follows. The rest of the introduction
presents van Lambalgen's and Raatikainen's arguments against Chaitin's
interpretation. A brief discussion of the possibility to draw extra-logical
conclusions from theorems of logic follows, and finally there is a summary
of two previously unpublished papers, that constitute the main part of the
thesis. The first of these papers reinforces the criticism of the standard
interpretation of the constant in Chaitin's theorem. The second paper, the
main paper of the thesis, is of a more positive nature, and there we show
how to construct a measure of some extensions of Peano Arithmetic. These two
papers are separately written, and they contain some overlappings. There are
also some overlappings between the introduction and the two papers. This has
the advantage that the introduction and the two papers can be separately
studied, but the disadvantage of some tiresome repetitions. We apologize for
that.
Some Arguments Against the Received Interpretation of Chaitin's Theorem
That the philosophical conclusion of Chaitin's theorem is problematic,
is one of the themes in an excellent paper by van Lambalgen [vL89]. In
this paper he assumes that to every formal system S, which contains
elementary arithmetic, there is a minimal constant c_s , the
characteristic constant of S, such that S does not prove any theorem of
the form K(n) > c_s , in symbols S \-/ K(n) > c_s , or more exactly a
formula representing the relation K(n) > c_s. As above K(n) is the
Kolmogorov complexity of the string n. 3
In the paper referred to above, van Lambalgen shows that there is
no connection between the information content of a theory S and the
characteristic constant c_s associated with the theory. Where Chaitin
usually denines the Kolmogorov complexity with concepts like 'abstract
computer' or 'Turing machine', van Lambalgen in his discussions uses
partial recursive functions, but this change of concepts does not affect
the argument. Here we will briefly sketch a proof by van Lambalgen
showing that the characteristic constant depends on the Godel numbering
of the partial recursive functions. Let Y_e be the partial recursive
function with index e, and define K_ye (n) = min{l(p) : Y_e (p) = n},
where l(p) is the length of the binary string p. It is easy to define a
bijection between binary strings and natural numbers. This makes it
possible to speak of the complexity of a number. If the p in K_ye(p) is
a number, then l(p) = p. 4
Like van Lambalgen, Raatikainen identifies the origin of the misuse
of the incompleteness theorem by the confusing of object language and
metalanguage, but the discusses this in terms of "use" and "mention".
In the following sentence about the dog Fido, the first occurrence of
'Fido' is use and the second is mentioned.
Fido has four legs, and 'Fido' contains four letters.
1.3 What Extra-Logical Conclusions Can Be Drawn from a Theorem of Logic?
Knowing that Chaitin's philosophical conclusions from his incompleteness
theorem are not warranted, it is interesting to ask if it is possible to
draw extra-logical conclusions from a theorem of logic. Here we just
intend to formulate some stray remarks, because this is a problem that
is too large for this thesis. It is not an exaggeration to say that
Godel's incompleteness theorems are the theorems mostly used, or misused,
in this context. To give a well-known example we can mention Hofstadter.
In the last chapter of [Hof79] he discusses `consequences' of Godel's
two incompleteness theorems, and he is very explicit in saying that
these theorems do not prove anything in e.g. psychology. At the same
time he thinks that the theorems can reveal new truths if they are used
metaphorically. Hofstadter thinks that the brain and the thinking, the
acitivity of the mind, can be considered from a high, 'soft ware' level
that contains concepts that cannot be seen at lower, 'neuron' levels,
and that this high level might have an explaining capacity that cannot
exist at lower levels. In a way, he equates this with the 8 In [Raa01]
a way, he equates this with the translation of number theory into
metamathematics, and postulates that it is something like this that
gives rise to our unanalysable feelings of the I.
In a way, not discussed by Dummet, we know exactly which structure this
is anyhow, because the natural numbers can be characterized up to
isomorphism in second order Peano Arithmetic, as was proved by Dedekind.
A large part of Dummet's paper is devoted to discussions of the meaning
of 'natural number', and he wants to know what light is thrown by
Godel's theorem on the meaning of `natural number' in so far as
understanding its meaning involves grasping the application of the
predicate 'true' to arithmetical sentences.
After a digression into different ways of attaching meaning to 'natural
num-ber', and a short discussion of the bearing of the ideas presented
on intuitionism, Dummet comes to the conclusion that
(t)he intuitive conception of a valid mathematical proof ... cannot
in general be identified with the concept of proof within some formal
system, for it may be the case that no formal system can ever succeed
in embodying all the principles of proof that we should intuitively
accept; and this is precisely what is shown to be the case in regard
to number theory by Godel's theorem.
Finally, as a support for his intuitionistic claims, he says that the
intuitionists are right in claiming that, if the sense of mathematical
statements is to be given in the notion of mathematical proof, it
should be in terms of the inherently vague notion of an intuitively
acceptable proof, and not in terms of a proof within any formal system.
9 Views akin to Hofstadter's can be found in e.g. [Pen89] and [Ruc95].
Rucker's book was originally published in 1982. In [Web80] there are
extensive discussions of arguments for and against using Godel's
theorems, Church's Thesis, and Church's and Turing's results
on decidability as support for mentalism, mechanism, etc.
QA9.8 .W4. Webb, Judson Chambers, 1936- ; Mechanism, mentalism, and
metamathematics : an essay on finitism / Judson Chambers Webb.
INCOMPLETENESS, MECHANISM, AND OPTIMISM. STEWART SHAPIRO. Overview.
Philosophers and mathematicians have drawn lots of conclusions from
Godel's ... www.math.ucla.edu/~asl/bsl/0403/0403-002.ps
.
- Follow-Ups:
- Re: Raatikainen's Paper on Chaitin
- From: Stephen Harris
- Re: Raatikainen's Paper on Chaitin
- References:
- Raatikainen's Paper on Chaitin
- From: Daryl McCullough
- Raatikainen's Paper on Chaitin
- Prev by Date: Re: Question on Chaitin
- Next by Date: Re: Question on Chaitin
- Previous by thread: Raatikainen's Paper on Chaitin
- Next by thread: Re: Raatikainen's Paper on Chaitin
- Index(es):
Relevant Pages
|
