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 onecannot solve the halting problem for a particular algorithm.And unless you prove that that particular algorithm is undecidableIf it's undecidable that means its either false or true butcontains no proof, that is to say it's truth can't be demonstratedin a finite number of steps. And Turing proved that there are ainfinite number of undecidable statements that you can not know areundecidable.> then it is still possible to find another algorithm that coulddecide on the halting of that algorithm.There might be such a algorithm for a given problem or there mightnot be, and if there isn't you can't know there isn't so you willkeep looking for one forever and you will keep failing forever.>>If you see it stop then obviously you know that it stopped but ifits still going then you know nothing, maybe it will eventuallystop and maybe it will not, you need to keep watching and you mightneed 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 toGodel some statements are true but un-provable, if The GoldbachConjecture is one of these (and if its not there are a infinitenumber of similar statements that are) it means that it's true sowe'll never find a every even integer greater than 4 that is notthe sum of primes greater than 2 to prove it wrong, and it meanswe'll never find a proof to show it's correct. For a fewyears after Godel made his discovery it was hoped that we could atleast identify statements that were either false or true but had noproof. If we could do that then we would know we were wasting ourtime looking for a proof and we could move on to other things, butin 1935 Turing proved that sometimes even that was impossible.Are there any explicitly known arithmetic propositions which must betrue or false under Peanao's axioms, but which are known to beunprovable? If we construct a Godel sentence, which corresponds to"This sentence is unprovable.", in Godel encoding it must be anarithmetic proposition. I'm just curious as to what such anarithmetic proposition looks like.

I forgot to mentioned also the famous Goodstein sequences: http://en.wikipedia.org/wiki/Goodstein_theorem

`Goodstein sequences are sequences of numbers which always converge to`

`zero, but PA cannot prove this, although it can be proved in second`

`order arithmetic.`

`You can google also on "hercule hydra undecidable" to find a game,`

`which has a winning strategy, but again this is not provable in PA.`

`But "machine theologians" are not so much interested in those`

`extensional undecidable sentences (in PA), as they embrace the`

`intensional interpretation of the undecidable sentence, like CON(t),`

`(<>t).`

Bruno

BrentIf Goldbach is un-provable we will never know it's un-provable, weknow that such statements exist, a infinite number of them, but wedon't know what they are. A billion years from now, whatever hyperintelligent entities we will have evolved into will still be deepin thought looking, unsuccessfully, for a proof that Goldbach iscorrect 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 GoogleGroups "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 GoogleGroups "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.