On 16 Aug 2012, at 22:11, meekerdb wrote:
On 8/16/2012 12:32 PM, John Clark wrote:
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.
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.
Some problem like that have been studied by Paris and Harrington. A
famous problem by Ramsey has lead to undecidability in Peano
Arithmetic. This is explained notably in the following book:
http://www.ams.org/bookstore?fn=20&arg1=whatsnew&ikey=CBMS-45
You can google on Ramsey undecidable Peano, for more on this.
Bruno
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-
l...@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
.
http://iridia.ulb.ac.be/~marchal/
--
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.