William Hughes wrote:

Sue wrote:

"Jim Ferry" <corklebath@hotmail.com> wrote in message
news:1158263413.708768.123050@p79g2000cwp.googlegroups.com...

jaapsch wrote:

Proginoskes wrote:

Panties On Head wrote:

[...]
The word random is horribly ambiguous. [...]

Not really. The computer science definition is: A(n infinite) sequence
is random if no algorithm can generate the sequence. Since there are
only countably many algorithms, that means that over 99% of the
sequences are random. (You can replace 99 with any integer < 100.)

I don't like that definition at all.
Suppose a_n is such a random sequence. Define another sequence by b_2n
= a_n, and b_(2+1) = 0.
There is still no algorithm that can generate all of sequence b, but I
would not call sequence b random, since there is a very simple way to
generate half its numbers.

Good definitions of what it means to be a random sequence are given in
http://arxiv.org/PS_cache/math/pdf/0110/0110086.pdf

Essentially, a sequence is random if it cannot be compressed, so the
addition of the extraneous zeros makes the sequence non-random.

[...]

Actually it is quite accurate. To be more exact. Let A be a random
(noncompressible) sequence. Let B be a sequence of zero's, the same
length as A. Let C be the sequence formed by interleaving A and B.
Then C is cleary compressible (by about 50%) and is non-random
(even though there is no way of "predicting" every second element of
C).

There are several ways used to define computable functions on
N or N^k. I think it's fair to say that definitions that use
Turing machines are popular for their intuitive appeal.

Rado introduced the "Busy Beaver" contest, where all
Turing machines with the same number of states are entrants
and the winner(s) of the n-state contest are those that
halt starting with a blank tape, while leaving a maximal
number of '1' symbols on the tape once they have halted.

The kind of Turing machines considered by Rado have
two tape symbols (blank and dash, or 0 and 1). Also,
after reading a tape symbol, a TM first writes something
to the tape, then moves one square to the right or to
the left, and ends up in a state given in its program.
This leads to transition tables made of 5-tuples, where
each 5-tuple has two inputs and three outputs (symbol
written, direction read head is moved and next state).

Let's say we call "Rado set of order n" the set of
all the possible number of '1' symbols left on the
tape of a halting n-state TM, once it has halted.

Then, the maximal element in the "Rado set of order n"
is by definition Sigma(n), Sigma being the usual
Busy Beaver function. The Rado set of order n
is finite, so its complement in N is infinite.
The question I thought of is this: n being fixed,
what is the smallest natural number in the
complement of the Rado set of order n?

In other words, given n, what is the least k>=0 such
that no TM with n states that halts will leave k '1'
symbols on the tape once it has halted?

So for n=100 for example, the corresponding k would
be a small "incompressible" number.

For n=1, the Rado set consists of 0 and 1. So the least
number in the complement is 2. For n=2, the Rado set contains
0, 1, 2 and 4, and maybe 3 (I don't know about 3 ... ) .
So the smallest element in the complement of the Rado set of
order 2 is either 3 or 5.

Ref.: Allen Brady, ``The Busy Beaver Game and the Meaning
of Life", in ``The Universal Turing Machine A Half-Century
Survey", Rolf Herken, Editor.

David Bernier