Re: new to extropy:question

John Clark (
Tue, 3 Nov 1998 12:31:06 -0500

Hash: SHA1

Michael Fitzgerald <> Wrote:

>question: could someone please try to explain to me -in terms adapted to
>the level of mathmatical aptitude suggested by foregoing- the proof
>offered by Tipler on p.26 of Physics of immortality, that is, the
>argument he offers to prove that the Halting problem is unsolvable.

I wrote about that and some other stuff in my dialog "Waiting For Zed" that was on Extropy Online, this is part of it.


Bob: You are quite correct, a computer can't do everything, it can't even

     handle some numbers, Alan Turing discovered those numbers and then used
     them to prove that no computer program can ever predict if it will ever
     be able to come up with a solution to a problem, much less predict what
     that answer will be. This is how Turing proved that a computer can not
     deal with all numbers or even most numbers. First make a list of all
     possible binary computer programs.

Alf: This Turing character, if he ever really existed, sure did a lot, but
     this list of his is going to be awful big, infinitely large in fact.

Bob: Alan Turing isn't just credited with writing "The Iliad" he was also a
     great mathematician, he laid the foundation of computer science and broke
     the nazi military code in his spare time. Yes, he was well aware that his
     list of all possible binary computer programs would be infinitely large,
     it does not flaw his proof.

     If the programs don't have an endless loop in them they will eventually
     spit out a digital output of some sort when you run them, we will treat
     this binary output as a number, so that program Pn produces the binary
     number bn1 bn2 bn3 ...   Sometimes the output will be infinitely long,
     like Pi, that's OK, write  it all down. Sometimes the program will have
     no output at all because it is caught in an  endless loop, in that case
     just put in a blank line in  the list. This is how the list would look.

     Program P1 outputs bits  b11 b12 b13 b14 b15 ... etc
     Program P2 outputs bits  b21 b22 b23 b24 b25 ... etc
     Program P3 outputs bits  b31 b32 b33 b34 b35 ... etc
     Program P4 outputs bits  d41 d42 d43 d44 d45 ... etc
     Program P5 outputs bits
     Program P6 outputs bits  b61 b62 b63 b64 b65 ... etc

     Now we can come up with our non computable number, all we need is to
     apply the "not" (~) operator in a diagonal manner on our list. The
     following number is non computable ~b11 ~b22 ~b33 ~b44 ...   Program P1
     will not produce bit ~b11, program P2 will not produce bit ~b22  Program
     P3 will not produce bit ~b33 etc. No computer program will ever produce
     this number, not even in an infinite amount of time.

Alf: Hold on! Everything you've said looks pretty mechanical to me, so why
     couldn't a computer program produce it? To find the nth bit of our non
     computable number all you need to do is run the Pn computer program
     until it produces the nth bit and then "not" it. Now we have a computer
     program producing a number that no computer program can produce.
     Something is not right.

Bob: Correct, something stinks. The only solution to the paradox is that in
     general the Halting Problem must not have a solution. This means you
     can't know for sure if the program will ever produce the nth bit.
     It might go into an endless loop, it might not. It might produce the
     nth bit in 5 seconds, it might produce it in 5 billion years, it might
     never produce it. There is no general algorithm to decide, that means
     that a computer program can never know if it will find a solution to a
     problem or what it will do next until it actually does it.


John K Clark

Version: PGP for Personal Privacy 5.5.5

iQA/AwUBNj892t+WG5eri0QzEQJj4gCg7XOr7xD4apxbzCOIQIBs6uUPsCoAoN9r LMOg/EPlE0461pjAmOMja9WV