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