2. Self-sizing programs.
How do programs influence their own size?
They can keep small by (1) avoiding requests for new
oracles (e.g. by avoiding jumps to the current 
),
and (2) by using Allocate and Free
in a balanced way.
Oracle requests,
Allocate and Free provide the only ways
of influencing the number of ``visible'' legal
addresses available in used storage.
The oracle requests are the only source of randomness, however.
If the current program does not request many
oracles, its space probability will tend to remain low,
although the program may perform extensive computations.
The bigger the used storage, however, the smaller
the probability of
guessing a particular ``visible'' address,
and the less
likely the arguments of instructions (like ``Jumleq'')
generated by future oracle requests.
Small is beautiful (more probable).
3. Probabilistic setting. Why use a probabilistic search algorithm instead of the original universal search procedure? One reason is to avoid unintended bias. For instance, unintended bias may be introduced by imposing a systematic (say, alphabetic) order among programs with equal quotients of probability and runtime. A drawback of the probabilistic version above, however, is that programs with low Levin complexity (in general) will be tested more than once.
When speed is an issue, then we will prefer systematic enumeration, or a slightly more complicated probabilistic variant whose expected search time equals the one of systematic enumeration (variants of systematic universal search based on the primitives above were implemented in collaboration with Norbert Jankowski (1994) and Stefan Heil (1995)). With the examples below, however, total search time is not the main issue: the simulations in the next section (based on probabilistic search) are intended to highlight generalization performance, not speed. Very similar results were obtained by systematic search.