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

**Date:** Wed Oct 14 2009 - 11:31:46 MDT

**Next message:**Robin Lee Powell: "Re: [sl4] Alan Turing's results are profound"**Previous message:**Marc Warner: "Re: [sl4] Alan Turing's results are profound"**In reply to:**Bradley Thomas: "RE: [sl4] Alan Turing's results are profound"**Next in thread:**Robin Lee Powell: "Re: [sl4] Alan Turing's results are profound"**Reply:**Robin Lee Powell: "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 ]

On Wed, 14 Oct 2009 "Bradley Thomas" <brad36@gmail.com> said:

*> Or are you saying something stronger than the above claim, that I'm overlooking,
*

*> that would require Turing's proof?
*

I'm saying Turing's proof is one of the most important in mathematics

and it makes me mad when people act like it's something trivial. For

example take the Goldbach Conjecture, it states that every even number

greater than 4 is the sum of two primes greater than 2. Let's try it for

some numbers:

6=3+3

8=5+5

10=3+7

12=5+7

14=3+11

16=3+13

18=7+11

20=3+17

22=5+17

24=7+17

26=7+19

28=11+17

30=11+19

This all looks very promising, but is it true for all even numbers?

Checking all even numbers one by one would take an infinite number of

steps, to test it in a finite number of steps I need a proof, but I

don't have one, nobody does. Perhaps nobody has found any Goldbach

Derivations even after looking for hundreds of years because it's not

true. It could be, but modern computers have looked for a

counterexample, they've gone up to a trillion or so and it works every

time. Now a trillion is a big number but it's no closer to being

infinite than the number 1 is, so perhaps The Goldbach Conjecture will

fail at a trillion + 2 or a trillion to the trillionth power. It's also

possible that some brilliant mathematician will come up with a proof

tomorrow, as happened with Fermat's last theorem, but there is yet

another possibility, it could be un-provable.

The Goldbach Conjecture is either true or it's not, Godel never denied

that, the question is, will we ever know if it's true or not? According

to Godel some statements are un-provable, if The Goldbach Conjecture is

one of these it means that it's true so we'll never find a

counterexample to prove it wrong, and it means we'll never find a proof

to show it's correct. For a few years after Godel made his discovery it

was hoped that we could at least identify statements that were either

false or true but had no proof. If we could do that then we would know

we were wasting our time looking for a proof and we could move on to

other things, but in 1935 Turing proved that sometimes even that was

impossible.

If Goldbach is un-provable we will never know it's un-provable, Godel

told us that such statements exist but he didn't tell us what they were.

A billion years from now, whatever hyper intelligent entities we will

have evolved into will still be deep in thought looking, unsuccessfully,

for a proof and still grinding away at numbers looking, unsuccessfully,

for a counterexample. And if Goldbach is't un-provable Turing tells us

there are an infinite number of similar statements that are.

Sometimes I wonder if that's why Turing killed himself and Godel died

insane.

John K Clark

*>
*

*>
*

*> 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
*

*>
*

-- John K Clark johnkclark@fastmail.fm -- http://www.fastmail.fm - Faster than the air-speed velocity of an unladen european swallow

**Next message:**Robin Lee Powell: "Re: [sl4] Alan Turing's results are profound"**Previous message:**Marc Warner: "Re: [sl4] Alan Turing's results are profound"**In reply to:**Bradley Thomas: "RE: [sl4] Alan Turing's results are profound"**Next in thread:**Robin Lee Powell: "Re: [sl4] Alan Turing's results are profound"**Reply:**Robin Lee Powell: "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:05 MDT
*