On 20 Jun 2012, at 19:37, John Clark wrote:
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.
Correct.
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,
Yes. That is part of Arithmetical Realism.
but he was investigating if we can always obtain that one bit of
information for any program and he proved we can not.
Indeed.
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.
Sure.
> 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.
Yes. But nowhere I said that we would knowingly get the decimals
correct, only that we would get the decimal correct after a finite
(even if unknown) time.
Bruno
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.
