On Wed, Aug 15, 2012 at 2:24 PM, Quentin Anciaux <allco...@gmail.com> wrote:

I have to say it again, it doesn't mean that a particular one cannot solve
> the halting problem for a particular algorithm.

 And unless you prove that that particular algorithm is undecidable

If it's undecidable that means its either false or true but contains no
proof, that is to say it's truth can't be demonstrated in a finite number
of steps. And Turing proved that there are a infinite number of undecidable
statements that you can not know are undecidable.

> > then it is still possible to find another algorithm that could decide on
> the halting of that algorithm.

There might be such a algorithm for a given problem or there might not be,
and if there isn't you can't know there isn't  so you will keep looking for
one forever and you will keep failing forever.

>>If you see it stop then obviously you know that it stopped but if its
>> still going then you know nothing, maybe it will eventually stop and maybe
>> it will not, you need to keep watching and you might need to keep watching
>> forever.
> > It's obviously not true for *a lot* of algorithm....

Yes, but it is also true for *a lot* of algorithms. According to Godel some
statements are true but un-provable, if The Goldbach Conjecture is one of
these (and if its not there are a infinite number of similar statements
that are) it means that it's true so we'll never find a every even integer
greater than 4 that is not the sum of  primes greater than 2 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, we know
that such statements exist, a infinite number of them, but we don't know
what they are. 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 that Goldbach is correct and still be grinding
away at numbers looking, unsuccessfully, for a counterexample to prove it

  John K Clark

You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to everything-list@googlegroups.com.
To unsubscribe from this group, send email to 
For more options, visit this group at 

Reply via email to