On 27 Aug 2012, at 15:15, Richard Ruquist wrote:
Is it true that real numbers are complete?
It is true that the first order theory of the real numbers, is complete.
This has been proven by Tarski.
Now add some trigonometric function axioms, and you are incomplete
again, as the trigonometric functions will re-instantiate the natural
numbers, by equation like sin(2PI*x) = 0. To be short.
yes, from a first order logic perspective: the real numbers (R, + x)
are simpler than (N, +, x), as the second are Turing universal, the
first are not.
Bruno
Richard
On Mon, Aug 27, 2012 at 9:11 AM, Bruno Marchal <marc...@ulb.ac.be>
wrote:
On 27 Aug 2012, at 11:47, Alberto G. Corona wrote:
Please don´t take my self confident style for absolute certainty. I
just expose my ideas for discussion.
The fascination with which the Gödel theorem is taken may reflect
the atmosphere of magic that invariably goes around anything for
which there is a lack of understanding. In this case, with the
addition of a supposed superiority of mathematicians over machines.
I have never really herad about a mathematician or a logician
convinced by such an idea.
What Gödel discovered was that the set of true statements in
mathematics, (in the subset of integer arithmetics) can not be
demonstrated by a finite set of axioms. And to prove this, invented
a way to discover new unprovable theorems, given any set of axioms,
by means of an automatic procedure, called diagonalization, that the
most basic interpreted program can perform. No more, no less.
Although this was the end of the Hilbert idea.
OK.
What Penrose and others did is to find a particular (altroug quite
direct) translation of the Gódel theorem to an equivalent problem in
terms of a Turing machine where the machine
Translating Gödel in term of Turing machine is a well known
pedagogical folklore in logic. It is already in the old book by
Kleene, Davis, etc. It makes indeed things simpler, but sometimes it
leads to misunderstanding, notably due to the common confusion
between computing and proving.
does not perform the diagonalization and the set of axioms can not
be extended.
That's the case for the enumeration of total computable functions,
and is well known. I am not sure Penrose find anything new here.
Penrose just assumes that Gödel's theorem does not apply to us, and
he assumes in particular than humans know that they are consistent,
without justification. I agree with Penrose, but not for any form of
formalisable knowledge. And this is true for machines too.
By restricting their reasoning to this kind of framework, Penrose
demonstrates what eh want to demonstrate, the superiority of the
mind, that is capable of doing a simple diagonalization.
IMHO, I do not find the Gödel theorem a limitation for computers. I
think that Penrose and other did a right translation from the Gódel
theorem to a problem of a Turing machine,. But this translation can
be done in a different way.
It is possible to design a program that modify itself by adding new
axioms, the ones produced by the diagonalizations, so that the
number of axioms can grow for any need. This is rutinely done for
equivalent problems in rule-based expert systems or in ordinary
interpreters (aided by humans) in complex domains. But reduced to
integer aritmetics, A turing machine that implements a math proof
system at the deep level, that is, in an interpreter where new
axioms can be automatically added trough diagonalizations, may
expand the set of know deductions by incorporating new axioms. This
is not prohibited by the Gódel theorem. What is prohibited by such
theorem is to know ALL true statements on this domain of integer
mathematics. But this also apply to humans. But a computer can
realize that a new axiom is absent in his initial set and to add it,
Just like humans.
I do not see in this a limitation for human free will. I wrote about
this before. The notion of free will based on the deterministc
nature of the phisics or tcomputations is a degenerated, false
problem which is an obsession of the Positivists.
Got the feeling I have already comment this. yes, Gödel's proof is
constructive, and machines can use it to extend themselves, and John
Myhill (and myself, and others) have exploited this in many ways.
Gödel's second incompleteness theorem has been generalized by Löb,
and then Solovay has shown that the modal logical systems G and G*
answer all the question at the modal propositional level. For
example the second incompleteness theorem <>t -> ~[]<>t is a theorem
of G, and <>t is a theorem of G*, etc.
Gödel's theorem is not an handicap for machine, on the contrary it
prevents the world of numbers and machines from any normative or
"totalitarian" (complete- theory about them. It shows that
arithmetical truth, of computerland, is inexhaustible.
Incompleteness is a chance for mechanism, as Judson Webb already
argued.
Bruno
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to the Google
Groups "Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com
.
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
.
--
You received this message because you are subscribed to the Google
Groups "Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com
.
For more options, visit this group at http://groups.google.com/group/everything-list?hl=en
.
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en.
