As mentioned
in Section 2 during the discussion of the
distribution issue,
one can define a distribution on all binary strings
by first selecting lengths and then selecting strings
of that length. Although it is mathematically impossible to
select strings with equal chance
from an infinite sample space,
strings of the same length can be selected with equal likelihood.
It is also impossible to select integers
from 
with the same probability,
but we can select
an integer with a probability close to being ``uniform.''
The second requirement in the above definition
guarantees that almost every length gets a ``fair''
degree of
probability weight.
It is important to note that for the purpose of
proving completeness
results, 
is the only requirement needed
since domination allows a polynomial factor,
and so some longer
strings can be given more weight than shorter ones.
Levin [Lev86] used 
for 
for notational
convenience (normalized by dividing by
), and
is often referred to as
the default uniform distribution.
