4
$\begingroup$

Is there a nice example of a sequence that looks random to any predictor whose predictions use a finite-state machine?

More precisely, consider a finite-state machine $M$ with input alphabet {0,1} and output alphabet {0,1}; each time it reads a new bit in its input stream, it updates its state and writes a new bit to its output stream (which should be interpreted as its prediction of the value of the next input bit). We seek a sequence of bits such that no matter what machine $M$ reads it, the input and output streams of $M$ agree asymptotically half the time. Such a sequence cannot be created by any finite-state mechanism (i.e. cannot be preperiodic), but perhaps it can be generated using a model of computation only slightly stronger.

Also, are there extant theories of weakened randomness relative to very limited models of computation?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ In relation to “but perhaps it can be generated using a model of computation only slightly stronger”, at least, we know that it can be generated in general (using a Turing Machine). As clearly stated in Wikipedia (en.wikipedia.org/wiki/…): “normal sequences are precisely those that appear random to any finite-state machine”. Thus, in fact we need any computable normal number (e.g. Veronica Becher and Santiago Figueira. An example of a computable absolutely normal number. Theoretical Computer Science, 270:947–958, 2002). $\endgroup$
    – Waldemar
    Oct 4, 2013 at 11:49

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.