On 8/17/2012 2:43 AM, Bruno Marchal wrote:

## Advertising

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<mailto:allco...@gmail.com>> wrote:I have to say it again, it doesn't mean that a particular one cannot solve thehalting 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 but contains no proof, that isto say it's truth can't be demonstrated in a finite number of steps. And Turing provedthat there are a infinite number of undecidable statements that you can not know areundecidable.> 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 ifthere isn't you can't know there isn't so you will keep looking for one forever andyou 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 statementsare true but un-provable, if The Goldbach Conjecture is one of these (and if its notthere are a infinite number of similar statements that are) it means that it's true sowe'll never find a every even integer greater than 4 that is not the sum of primesgreater than 2 to prove it wrong, and it means we'll never find a proof to show it'scorrect. For a few years after Godel made his discovery it was hoped that we could atleast identify statements that were either false or true but had no proof. If we coulddo that then we would know we were wasting our time looking for a proof and we couldmove on to other things, but in 1935 Turing proved that sometimes even that wasimpossible.Are there any explicitly known arithmetic propositions which must be true or falseunder Peanao's axioms, but which are known to be unprovable? If we construct a Godelsentence, which corresponds to "This sentence is unprovable.", in Godel encoding itmust be an arithmetic proposition. I'm just curious as to what such an arithmeticproposition looks like.I forgot to mentioned also the famous Goodstein sequences: http://en.wikipedia.org/wiki/Goodstein_theoremGoodstein sequences are sequences of numbers which always converge to zero, but PAcannot prove this, although it can be proved in second order arithmetic.

`I'd say they are not part of arithmetic, since they are generated by substituting one`

`number for another - not an arithmetic operation. So I find it hard to see "Goodstein`

`sequences terminate in zero." as a proposition of arithmetic or number theory. It seems`

`that they depend on positional notation.`

Brent

You can google also on "hercule hydra undecidable" to find a game, which has a winningstrategy, but again this is not provable in PA.But "machine theologians" are not so much interested in those extensional undecidablesentences (in PA), as they embrace the intensional interpretation of the undecidablesentence, like CON(t), (<>t).BrunoBrentIf Goldbach is un-provable we will never know it's un-provable, we know that suchstatements exist, a infinite number of them, but we don't know what they are. Abillion years from now, whatever hyper intelligent entities we will have evolved intowill still be deep in thought looking, unsuccessfully, for a proof that Goldbach iscorrect and still be grinding away at numbers looking, unsuccessfully, for acounterexample to prove it wrong.John K Clark --You received this message because you are subscribed to the Google Groups "EverythingList" group.To post to this group, send email to everything-list@googlegroups.com.To unsubscribe from this group, send email toeverything-list+unsubscr...@googlegroups.com.For more options, visit this group athttp://groups.google.com/group/everything-list?hl=en.--You received this message because you are subscribed to the Google Groups "EverythingList" group.To post to this group, send email to everything-list@googlegroups.com<mailto:everything-list@googlegroups.com>.To unsubscribe from this group, send email toeverything-list+unsubscr...@googlegroups.com<mailto: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/ <http://iridia.ulb.ac.be/%7Emarchal/> --You received this message because you are subscribed to the Google Groups "EverythingList" 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.