random

[David C. Ullrich]

On 6 Jun 2001 18:58:55 GMT, urpala at ampeeri.ee.tut.fi (Uoti Urpala)
wrote:

>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?".

Ok. The other day defining the silly syntax I was forgetting about
the "input stream" to the "program". There's no problem modifying
what I said to have one of those, exactly as you say here: The
first 1 marks the end of the "program" and the rest of the tape
is input to the program.

Satisfies everything you've said except for the requirement
that arbitrary binary data be included in the program with
a minimial number of bits.

>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. 

This makes a lot more sense (to me, today) than a certain sentence of
Chaitin's that was intended to say the same thing. Thanks.

>he
>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).

No halting program can be a prefix of another is exactly the
first thing I realized about what must be required to make the
thing work at all. Now the programs are the leaves of a certain
binary tree, and any infinite binary tree can be taken as the
encoding (as long as there are infinitely many leaves and the
branches of infinite length form a set of measure zero).

Then I realize that there is a simple binary tree that
makes this scheme reduce to the one where the n-th bit
of Omega is 1 iff the n-th TM halts. Leading to the
question of just what the rules are to get Chaitin's
magical results...

Preciate the clarification. When we have statements
about how "the probability that a random program
terminates has certain properties" and it turns out
that this depends very strongly on which definition
of "random program" we're using one wonders exactly
what the "rules" are. 

(If it were true just of one
particular encoding that would be silly. If it
were true of _any_ encoding, which is what I
thought for a day, that would be not silly at
all. When one finds that it is _not_ true for
just _any_ encoding but one sees credible
people saying it is then one _really_ wonders
what the rules are. If the requirements are
reallt just as above then I suppose I agree
the requirements are not that strong.)
 
>Uoti Urpala



David C. Ullrich
*********************
"Sometimes you can have access violations all the 
time and the program still works." (Michael Caracena, 
comp.lang.pascal.delphi.misc 5/1/01)