**From:** Bradley Thomas (*brad36@gmail.com*)

**Date:** Wed Oct 14 2009 - 09:54:55 MDT

**Next message:**John K Clark: "Re: [sl4] Alan Turing's results are profound"**Previous message:**Luke: "Re: [sl4] what's with all the math?"**In reply to:**John K Clark: "[sl4] Alan Turing's results are profound"**Next in thread:**John K Clark: "RE: [sl4] Alan Turing's results are profound"**Reply:**John K Clark: "RE: [sl4] Alan Turing's results are profound"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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

**Next message:**John K Clark: "Re: [sl4] Alan Turing's results are profound"**Previous message:**Luke: "Re: [sl4] what's with all the math?"**In reply to:**John K Clark: "[sl4] Alan Turing's results are profound"**Next in thread:**John K Clark: "RE: [sl4] Alan Turing's results are profound"**Reply:**John K Clark: "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:05 MDT
*