```X-Message-Number: 23892
Date: Wed, 14 Apr 2004 17:45:20 -0700
From: Mike Perry < var s1 = "mike"; var s2 = "alcor.org"; var s3 = s1 + "@" + s2; document.write("<a href='mailto:" + s3 + "'>" + s3 + "</a>"); >
Subject: Goedel, Turing, cryonics

Comments mainly on Robert Ettinger's posting #23870:

>As to the significance of Goedel's undecidability:  Undecidability can stem
>from more than one cause. In Goedel's case, it was just a trick of
>language or
>labels, and therefore of no real consequence. Undecidability for other
>reasons
>is a different story.

Goedel's undecidability is not *just* "a trick of language or labels"
(though I'll agree it is that, and a very pretty trick at that) but really
is intimately tied to the halting problem, as I said in an earlier posting.
For the main mathematical system Goedel worked with, Whitehead and Russel's
Principia Mathematica (PM) is able to construct sentences S equivalent to:
"the following Turing machine started with the following input will
eventually halt." If a formal decision procedure existed for PM, it would
be able to decide if S-type sentences were provable or not within PM, and
you could turn that into a solution of the halting problem. As for the
converse, suppose we use a computer (computationally equivalent to a Turing
machine) to start up a procedure of generating proofs of all provable
assertions in PM, and checking to see if any are proofs of some particular
assertion T. If any such proof is found, then execution stops, otherwise it
continues. So if we could solve the halting problem, we could tell if in
fact T is provable, and this could be turned into a decision procedure for
PM. (Yes, it would not be a very efficient procedure, if done exactly this
way, but that does not affect the validity of the conclusion.) This shows
the two results (undecidability, halting problem unsolvability) are not
just closely connected, but equivalent. If we grant that the halting result
is "significant," which I'll argue in a moment, then we have to concede
this for undecidability too.

Briefly, though, I can see another reason, independent of the halting
problem, for thinking of Goedel's result as very mathematically
significant, in that it shows in a formal, thus inescapable, way, that
certain very powerful, formal mathematical systems nonetheless have certain
basic limitations. (The result, by the way, extends to other mathematical
systems besides PM, and essentially, to any system in a large class that is
comprehensive enough to develop important parts of mathematics including
the theory of whole numbers. It is, in fact, the comprehensiveness of the
system that inevitably incorporates the weakness, as Goedel's result
shows--the weakness is upward-compatible. Other notions of "mathematical
system" are possible that get around this problem in some sense, but they
still leave basic questions unanswerable. I think it safe to say that most
mathematics is still done in systems of the PM variety that share the
weakness that Goedel proved exists.)

>The Halting problem: Why should anyone ever have assumed that any program
>would have the referenced property (ability, confronted with a specific
>program,
>to decide in a finite time whether that program would ever halt)?

Suppose I ask this question: Why would one ever assume that four colors
would not be enough to color a map in the plane? Yet proving this was still
significant. The much easier, but still nontrivial result of showing that
five colors is enough is even significant. But on the other hand, some
computer programs in some ways are *very* powerful, so who is to say that
there does not exist one so powerful as to be able to anticipate certain
aspects of the behavior of all possible programs, even including itself? At
any rate, it took some hard thinking to show this was impossible, for the
particular matter at hand, and that is significant.

>It is not
>news that an arbitrary program can have unexpected results, and that even the
>programmer cannot know for sure what will happen until the program runs long
>enough. It is also possible to write self-modifying programs, for example
>involving random or pseudo-random numbers, and it is hard to see how any
>prior
>program could deal with this.

Again, to say something is "hard to see" is not the same as saying that a
formal proof of it is impossible. I will also add that the real world
doesn't fit the Turing model that easily (or at all, as some would
vehemently argue), and there may be various "workarounds" for the
unsolvability of the halting problem. (I haven't seen any practical ones,
though.) And the real world is very important. But that doesn't change the
conclusion that the result is significant. Indeed, in some ways it
reinforces it, showing that certain formally defined systems do have
certain limitations, which otherwise we would not "know" to be true in the
real world, whatever our intuition may suggest.

It is worth adding here that, though I think Goedel's incompleteness
results are significant (in addition to undecidability he showed that an
internal proof of consistency is impossible if the system in question, say
PM, is in fact consistent), I would not go so far as some do. They argue
that they show that the human mind has powers inherently beyond those of
our machines. There are various arguments against this conclusion, ranging
from the idea that formally describable systems don't get useful results
simply by, in essence, proving infallible theorems, to noting that machines
(or any artificial constructs) are, like us, part of the real world and not
just abstractions. They thus have properties not necessarily described in
our formal systems. In any case they will, if suitably made, be "like us"
in some deep sense, which ought to go far in overcoming any limitations on
their performance as compared to that of humans.

To tie this in to cryonics: we are machines, of a certain sort. Certain
analogies hold. Cryopreservation puts the system, the human, a type of
machine, "on hold" so that skilled "mechanics" of the future, possessing
knowledge and techniques we don't have today, can get it restarted,
provided the preservation itself is adequate. Goedel's results may, if
misunderstood, cast doubt on whether we, creatures with minds, can be
considered machines, open to repair and restarting as with a car or
computer. This need not follow, but we want to give credit where it is due,
and note the profound implications and significance of these results.

Mike Perry

Rate This Message: http://www.cryonet.org/cgi-bin/rate.cgi?msg=23892

```