On 8/16/2012 12:32 PM, John Clark wrote:
On Wed, Aug 15, 2012 at 2:24 PM, Quentin Anciaux <allco...@gmail.com
<mailto: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.
Are there any explicitly known arithmetic propositions which must be true or false under
Peanao's axioms, but which are known to be unprovable? If we construct a Godel sentence,
which corresponds to "This sentence is unprovable.", in Godel encoding it must be an
arithmetic proposition. I'm just curious as to what such an arithmetic proposition looks
like.
Brent
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 wrong.
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
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en.
--
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
everything-list+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en.
