On Wed, Jun 20, 2012 at 3:39 AM, Bruno Marchal <marc...@ulb.ac.be> wrote:
>> It's true that if you knew the numerical value of Chaitin's Constant >> then you would know that if a 100 bit program had not stopped after a >> Turing Machine had run n number of finite operations then it never will; >> but the trouble is you don't know Chaitin's Constant and never can, so you >> can never know how big n is. So even though they have been running for a >> googoplex to the googoplex power years one of those programs could stop 5 >> seconds from now. >> > > > Not if I waited, by chance or whatever, a time bigger than BB(100). > Then it will never stop but you don't know it will never stop, so you'll still be looking to see if it stops in the next 5 seconds or the next 10 seconds or the next googoplex to the googoplex power years. Godel was a Platonist, he thought things were true or they were not he just said sometimes we can't know which, and Turing certainly believed all programs will come to a stop or they will not, but he was investigating if we can always obtain that one bit of information for any program and he proved we can not. Neither the Busy Beaver nor Chaitin's work on the Omega Constant changes that fact and is just more confirmation that Turing was right, not that more confirmation was needed, the proof is ironclad. > If a decimal change after that, then we got a computable function growing > more quickly than BB. > As I've said if a program of a given size has not stopped by a certain finite number of operations it never will, but that fact does you no good at all because to know what that finite number is you'd have to know Chaitin's Constant and you don't know that and never will. 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.
