random

[Uoti Urpala]

In article <3b1e43f4.1661099 at nntp.sprynet.com>, David C. Ullrich wrote:
>>requirements of the results. The encoding must allow "arbitrary binary
>>data" to be included. 

>consisting of all 0's terminated by a 1. Assunming that
>"arbitrary binary data" means only finitely much binary
>data that's no problem.

I meant that more literally: the encoding must allow binary data to be
included "as is", so that a constant of x bits takes no more than x
bits of program space.

>What I'm trying to track down is what does make the proof work.
>In particular what I'm curious about is whether the requirments
>that make the proof of the randomness work are really all that
>natural, or whether they were just chosen to make the randomness
>come out right in the end...

The requirements aren't all that strong. Basically, "self-delimited
turing-complete program with binary data" is enough. You first read
the program (with whatever self-delimited computable encoding, one
where the first 1 bit terminates as in your example above is OK). The
program can then read the following bits. "A random program
terminating" can then be defined as "select an infinite stream of
random bits; take the (if any) prefix that is a self-delimited
encoding; whenever the program reads a bit, give it the next one from
the stream; does the program ever halt?".

To work with finite programs-with-data in the above scenario, you can
define that a program trying to read more data than there is or trying
to halt before reading all the data fails (doesn't halt) - it wasn't
self-delimiting, as it didn't know the total length. The
must-read-all-data part allows simple calculation of lower bounds for
Omega, as it fixes the problem of the total being greater than 1 (no
halting program can be a prefix of another).

-- 
Uoti Urpala