random

[Uoti Urpala]

In article <3b1cf00f.5441109 at nntp.sprynet.com>, David C. Ullrich wrote:
>Indeed the exact value of Omega depends on the details of the
>encodings. What I'm wondering today is how many of his conclusions
>also depend on the details of the encoding.

>Suppose I have a syntax where a valid program is precisely
>a sequence of 0's terminated by a 1. Any such string is a
>valid program. Does this count as "self-delimiting"? 

That probably does count as self-delimiting, but it doesn't fill other
requirements of the results. The encoding must allow "arbitrary binary
data" to be included. The proof basically says "you need n bits of
program to calculate n bits of Omega". This is a strong result if the
encoding is efficient, but the above encoding needs a lot of bits to
calculate anything, so in that case the result doesn't say much about
the associated Omega (and the same proof wouldn't work, since it
depends on the ability to give an arbitrary program as an argument to
another with limited overhead).

Proving the randomness of Omega basically works like this:
You can create a program that, given the first n bits of Omega, solves
the halting problem for all programs of size <= n. (Details below)
If you can calculate the first m bits of Omega with a program of size
p, you can add a bit of extra code to create a program of size p+e (e
constant) that solves the halting problem for itself and then does the
opposite (the standard contradiction for a program solving the halting
problem for itself). So p+e must be greater than m to avoid a
contradiction, and a program to calculate the first m bits of Omega
must have size at least m-e. (You can generalize this to calculating
_any_ bits of Omega in whatever position - if you can calculate some
with a short program, you can hardcode the missing ones to get a full
initial segment).

Solving the halting problem for a program P of size s given the first
s bits of Omega:
Calculate lower bounds for Omega (as mentioned in other posts) until
the first s bits agree with the known bits. Now you have either found
that program P halts, or you know that it halting would raise the
lower bound so much that it could no longer match the known bits, so P
cannot halt.

Exercise: Show that the first bit of Omega whose value is independent
of ZFC is a 0.

-- 
Uoti Urpala