random

[Tim Peters]

Sorry for having dropped out of this thread -- one interesting question
leads to two, and simply ran out of time for it.  Just dropping in long
enough to reassure David on one point of pseudo contention:

[Tim]
>> (e.g., if the 0'th program happens to halt, that would imply
>> the halting probability is >= 1/2 across all programs -- but the 0'th
>> program isn't generally that smart <wink>).

[David C. Ullrich]
> Nope - this sounds good but it's specious. With the distribution
> I thought Chaitin was using it _would_ follow that Omega > 1/2
> if the 0-th program happened to halt, and with the distribution
> he _does_ use things that are equally winkie-sounding _do_
> follow:  Pick a program that does happen to halt. If that program
> is K bits long then the fact that that particular program halts
> _does_ show that Omega > 2^{-K}. That program happens to
> be smart enough to imply that the halting probability is
> larger than something - with a different distribution it would
> just imply that the halting probability is larger than a different
> thing.
>
> So I lied, but it's not as obvious as you say that my lie
> _must_ have been wrong - as long as we're just talking
> about "a random program" without specifying the distribution
> what I said could have been right regardless of questions of how
> smart the first program is.

All agreed.  I wasn't bothered that *a* program could "be that smart", but
"the 0th" program specifically:  it was pointing at the essential
arbitrariness of a measure that depends on how you just happen to tag the
machines with ordinals.  "Interesting" results in this (and related) field
are independent of labeling, so if Chaitin had come up with a result that
wasn't so independent, this thread never would have started <wink>.

>...
> That's the best excuse I can contrive. Oh well.

You don't need an excuse!  I wasn't careful with definitions, and was too
keen to keep this all at "fuzzy overview" level.  So that's my excuse.

> Thought I had the problem of inexact floating point solved.

Python beat you to it:  A real number is computable iff Python can compute
it.  Therefore you can enumerate the set of non-computable reals just by
picking them from the gaps in the ones Python can compute <wink>.

for-example-0.1-ly y'rs  - tim