From: John K Clark (johnkclark@fastmail.fm)
Date: Tue Oct 13 2009 - 23:27:30 MDT
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:04 MDT