From: Bradley Thomas (brad36@gmail.com)
Date: Wed Oct 14 2009 - 09:54:55 MDT
John, it seems to me that you are making this claim: a real
continually-running fixed-goal program must eventually reach an infinite
(and patterned, cyclic) loop in the absence of unpatterned
intervention/input that can somehow snap it out of the loop (e.g. a reboot).
I'm saying the claim is true since it is also true for the superset: all
real continually-running programs. The Turing proof is not necessary to
demonstrate your claim. It is true regardless of Turing's proof. Or are you
saying something stronger than the above claim, that I'm overlooking, that
would require Turing's proof?
Brad Thomas
www.bradleythomas.com
Twitter @bradleymthomas, @instansa
-----Original Message-----
From: owner-sl4@sl4.org [mailto:owner-sl4@sl4.org] On Behalf Of John K Clark
Sent: Wednesday, October 14, 2009 1:28 AM
To: sl4 sl4
Subject: [sl4] Alan Turing's results are profound
I confess to being a little shocked when somebody on this list said that all
Turing did was prove the trivial fact that a program like the one that
produced the digits of Pi will never halt. I was shocked at this
misunderstanding because I think Turing's results are some of the most
important in all of science. He proved that a computer, and by simple
extension a mind, can't do everything, it can't even handle some numbers.
Alan Turing discovered those numbers and then used them to prove that in
general no computer program can ever predict if it will be able to come up
with a solution to some problems, 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 to run on the
abstract computer that is now called a Universal Turing Machine. 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 produce
endless loops 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 blank
Program P6 outputs bits b61 b62 b63 b64 b65 ... etc
.
.
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
ProgramP3 will not produce bit ~b33 etc. No computer program will ever
produce this number, not even with infinite memory and with an infinite
amount of time at your disposal.
But you could quite correctly object to all this and insist that everything
I've said looks perfectly mechanical, so why couldn't a computer program
produce it? To find the nth bit of our so called 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. Something stinks. The only solution to the paradox
is that in general the Halting Problem must not have a solution. It means I
was pulling a fast one when I said "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" because you can never know if it deserves a
blank. It 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
in general 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
-- John K Clark johnkclark@fastmail.fm -- http://www.fastmail.fm - Access your email from home and the web
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:05 MDT