Re: A modern view of the halting problem

On 22 Oct 2006 15:15:08 -0700
"randyhyde@xxxxxxxxxxxxx" <randyhyde@xxxxxxxxxxxxx> wrote:

:"Gödel's Theorem has been used to argue that a computer can never be
:as smart as a human being

Your incorrect use of such citations shows that you need to visit
http://www.sm.luth.se/~torkel/eget/godel.html, but since you probably
won't, here are a few tidbits from the site:

Every day, Gödel's incompleteness theorem is invoked on the net to
support some claim or other, or just to whack people over the head with it
in a general way.
.. . .
Unsurprisingly, the bulk of these invocations covers a range from the
nonsensical to the merely technically inaccurate, and they often give rise
to a flurry of corrections and more or less extended technical or
philosophical disputes.
.. . .
There are two main types of references to stepping or standing "outside
the system" in connection with Godel's theorem, one of which is correct
and the other incorrect. These two categories will be illustrated by two
quotations.

First, a correct version:

"The mathematician Godel proved that a system of axioms can never be
based on itself: statements from outside the system must be used in order
to prove its consistency."

This makes good sense, since a consistent system T subject to Godel's
theorem can't prove its own consistency (or, equivalently, can't prove the
so-called Godel sentence for system T, which for all the usual systems T
is equivalent in T to "T is consistent"). Thus, to prove the consistency
of T it is necessary to "step outside the system" T in the sense of "bring
to bear some principle not contained in T itself". It should be noted,
however, that this does not mean that the consistency of T can only be
proved in a system stronger than T. All that follows is that to prove the
consistency of T, some principle must be used which is not contained in T
itself.

"Now an incorrect version:

"Godel's theorem states that in any consistent system which is strong
enough to produce simple arithmetic there are formulae which cannot be
proved-in-the-system, but which we [standing outside the system] can see
to be true."

On the net and elsewhere, one can one can expect to encounter many
startling claims about the implications of Godel's theorem for the powers
of the human mind. The following has actually appeared in print:

"Church's theorem states the existence of an absolutely undecidable
statement. This statement is produced by combining the Goedel sentences of
all formal systems together... Church took all those unprovable statements
and made one new statement from them, thereby arriving at a statement
which remains undecidable no matter what formal systems we introduce.
However, interestingly, even this "Church-sentence" is decidable by
humans: in fact it is pre-decided through its contruction by Church.
Church defined it so we can know: this statement is actually true. We can
demonstrate this truth but no formal system can."

It's unclear exactly what the author has in mind, but there is not in fact
any such "Church sentence". What is usually called Church's theorem states
that there is no algorithm for determining whether or not a sentence in
the formalism of predicate logic is logically valid.

.

Relevant Pages

  • Re: How to pronounce the word "Sagnac"
    ... To say "llan" (a Welsh church or parish), ... It is therefore incorrect to say any pronunciation is "British", ... Great Britain is made up of Wales, Scotland, the island of Ireland, ...
    (sci.physics.relativity)
  • Re: IGI Controlled extractions being removed (was Re: FreeREG search goes live?)
    ... just as C of E BMD record events in that church ... The comparison is incorrect. ... The CofE Baptism, Marriage, and Burial records ...
    (soc.genealogy.britain)
  • Re: Day Trips from Assisi
    ... boasts a very nice and important church.. ... the basilica of S.Maria degli Angeli ... incorrect. ... Within the Basilica there is the little Porziuncola ...
    (rec.travel.europe)
  • Re: Day Trips from Assisi
    ... boasts a very nice and important church.. ... incorrect. ... Within the Basilica there is the little Porziuncola ...
    (rec.travel.europe)