Re: Raatikainen's Paper on Chaitin


"Stephen Harris" <cyberguard1048-usenet@xxxxxxxxx> wrote in message
news:GNXie.766$mK.661@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx
>
> "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
>

Penrose writes:
I had vaguely heard of Godel's theorem prior [to the first year of
graduate school], and had been a little unsettled bymy impressions
of it . . . I had been disturbed by the possibility that there might
be true mathematical propositions that were in principle inaccessible
to human reason. Upon learning the true form of Godel's theorem . . .

"I was enormously gratified to hear that it asserted no such thing; for
it established, instead, that the powers of human reason could not be
limited to any accepted preassigned system of formalized rules."

I've started reading _The Digital Phoenix: How Computers
Are Chaning Philosophy_ edited by Bynum and Moor

Early in the introduction, these passages were combined
to produce what seems to me to be a dubious conlcusion.

"Leibniz believed that statements about complex things could be derived
from statements about their simpler components by a process analagous to
multiplication. Leibniz suggested that if fundamental concepts - a kind of
alphabet of human thought - could be isolated, all truths could be computed
from them. In principle, whenever humans differed in opinion on some
subject, they could sit down and calculate to determine the truth of the
matter. ...

In the twentieth century, the theory of computation has matured
and has had a striking impact upon philosophy. Alan Turing, the
brilliant British mathematician/philospher, developed a conception
of computation in terms of abstract mathematical devices, now
called "Turing Machines". His work, along with that of Alonzo
Church, Kurt Gödel and others, provided profound insights into
the nature and limits of logic and mathematics. The widely accepted
Church-Turing thesis states that whatever is computable is computable
by a Turing machine. Given this philosphical thesis, computation has
enormous possibilities and serious limitations. All computation can be
explained in terms of simple deterministic steps, but, as Turing proved,
some truths are not computable by Turing Machines.

*Therefore, Leibnitz's dream of having a universal calculus that would
allow us to resolve any difference in opinion through calculation cannot,
in principle, be fulfilled."

I repeat Penrose and compate it to * immediately above:

"I was enormously gratified to hear that it asserted no such thing; for
it established, instead, that the powers of human reason could not be
limited to any accepted preassigned system of formalized rules."

SH: How is it that Penrose cannot invoke Godel's argument to
refute strong AI but Godel's argument *can* be used to refute the
Leibniz dream of universal language formally mathematically expressed.

Isn't it the goal/belief of strong AI (top-down) that there is a program
written in a formalized language that can identically duplicate the human
capacity for reasoning by using a system of preassigned formalized rules?

Why is the view from "The Digital Phoenix" a correct usage of
Godel's Inc. theorem while Penrose made a big mistake? The
reasoning involved for rejecting Leibniz/formalize universal language
and for Penrose to reject a computer program that encompasses a formal
capacity to capture human reasoning seem to have the same basis?

A formalized language will run on a machine, so doesn't Leibniz's
program need to accomplish the same goal as strong AI, capturing
the full extent of human reasoning? It doesn't seem like there should
be opposite conclusions drawn about the ability of Godel Inc. to
refute the Leibniz dream but that same reasoning doesn't apply to
refuting Pensore/strong AI. Why doesn't the reasoning involved
produce consistent conclusions. Godel Inc. does not apply to
refuting Liebnize and Penrose or, Godel Inc. *does apply to refuting
both of their ideas? I think this is again a confusion of language and
metalanguage which is what Chaitin stands accused of for the
'no twenty-pound theorem from ten pound axioms.

"Now Chaitin's metaphor that "if one has ten pounds of axioms and
a twenty-pound theorem, then that theorem cannot be derived from
those axioms",

Daryl:
"What is true is that if T is a consistent theory whose complexity is K,
then T cannot *prove* that any theorem has complexity much greater than K.
But there will be theorems of T with complexity much greater than K."

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


.

Relevant Pages

  • OT: Church-Turing thesis (was Re: TCL cant do as much as Perl)
    ... Well, there's always the technical, trivial proof from Computer Science: either language can be used to simulate a Turing Machine, thus they are equally powerful, and no language can exist that is more powerful. ... the thesis states that a universal Turing machine (UTM) is able to compute any function which can be computed by an "effective method". ... An effective method is defined as being those tasks which an unaided human could in principle achieve, using just pencil and paper, following a finite number of instructions, in a finite number of steps, without using intuition etc. ...
    (comp.lang.tcl)
  • Re: Recursive language which is not context-sensitive
    ... language which is not context-sensitive: ... sensitive Grammar G and build up a turing machine T which accepts the ... down the 37th context sensitive grammar. ... is just a garbage string? ...
    (sci.math)
  • Re: Arthur ODwyer on the feasibility of simulating a Turing Machine
    ... > equivalent to Church's thesis re the Turing machine. ... that Marxists would attempt to get involved in mathematical philosophy. ... Initially writing represents speech, and it is very unusual to know how to ... However written language has its own ...
    (comp.programming)
  • Re: An uncomputability conjecture
    ... > language such as LISP or Prolog. ... > Turing machine that corresponds to R. ... let be the set of input words to ... we consider the possible uncomputability ...
    (comp.theory)
  • Re: Penrose vs the Robot
    ... I actually think now that Penrose' ... > is some robot with a Turing machine brain that is equivalent to ...
    (sci.logic)