Re: 31 bit pseudo-random number gen in C, C++ & d*** assembly code

It seems that the long time for these posts to show up is due to the
moderating in "comp.lang.c.moderated", so I'm taking this cross-post
out.

abariska@xxxxxxxxxxxxxxx wrote:
.....
> The random sequence decision question: does there exist a Turing
> machine that, given as input the finite segment of the sequence, can
> correctly determine the source (i or ii) with a probability of 1-delta,
> for any given delta > 0?

The above should have read "given as input the (infinite) sequence,
...." because I don't want to limit the Turing machine in its access to
the sequence. Anycase, it seems that there is no such Turing machine.
Idea of proof:

Assume there was, then you could feed it the input of a iid random
digit generator. After the Turing machine has accessed a finite segment
of the sequence (as it must if it is to decide the question in a finite
number of steps), it reaches the conclusion that the sequence is from
the random digit generator. If not (this happens with probability
delta), I simply run the test again until it answers correctly. With
probability 1 I only have to repeat the procedure a finite number of
times.

While it accessed the sequence, I jotted down every digit from the
sequence that it read. So I have all finite digits which the Turing
machine required to decide the question. Next, I simply construct
another Turing machine that reads out the tabulated digits. Because the
deciding Turing machine is deterministic, when faced with the output of
the table-reading Turing machine, it will again reach the conclusion
that the sequnce was from the random digit generator (and it won't
require more than the tabulated digits for this decision ). So, if
there was a Turing machine that could determine the correct answer with
probabiliy 1-delta for any delta > 0, I could construct another Turing
machine that resulted in a probability of error = 1, which is a
contradiction. Therefore no such deciding Turing machine can exist.

Regards,
Andor

.