**From:** John K Clark (*johnkclark@fastmail.fm*)

**Date:** Tue Oct 13 2009 - 23:27:30 MDT

**Next message:**Bradley Thomas: "RE: [sl4] I am a Singularitian who does not believe in the Singularity."**Previous message:**Arets Paeglis: "Re: [sl4] I am a Singularitian who does not believe in the Singularity."**In reply to:**Arets Paeglis: "Re: [sl4] I am a Singularitian who does not believe in the Singularity."**Next in thread:**Jordan Stewart: "Re: [sl4] Alan Turing's results are profound"**Reply:**Jordan Stewart: "Re: [sl4] Alan Turing's results are profound"**Reply:**Stuart Armstrong: "Re: [sl4] Alan Turing's results are profound"**Reply:**Bradley Thomas: "RE: [sl4] Alan Turing's results are profound"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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

**Next message:**Bradley Thomas: "RE: [sl4] I am a Singularitian who does not believe in the Singularity."**Previous message:**Arets Paeglis: "Re: [sl4] I am a Singularitian who does not believe in the Singularity."**In reply to:**Arets Paeglis: "Re: [sl4] I am a Singularitian who does not believe in the Singularity."**Next in thread:**Jordan Stewart: "Re: [sl4] Alan Turing's results are profound"**Reply:**Jordan Stewart: "Re: [sl4] Alan Turing's results are profound"**Reply:**Stuart Armstrong: "Re: [sl4] Alan Turing's results are profound"**Reply:**Bradley Thomas: "RE: [sl4] Alan Turing's results are profound"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*
This archive was generated by hypermail 2.1.5
: Wed Jul 17 2013 - 04:01:04 MDT
*