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 
For more options, visit this group at 

Reply via email to