X-Message-Number: 23892
Date: Wed, 14 Apr 2004 17:45:20 -0700
From: Mike Perry <>
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