An algorithm for enumerating subsequences of all infinite binary sequences?

69 Views Asked by At

We consider that an infinite binary sequence $s$ is not random in the sense of Martin-Löf.

For all the $s$ sequences which respect this constraint, is it possible to build an algorithm which can enumerate (in a set of indices $I$) all the positions of the numbers 1 in the sequence $s$ ?

If this is the case, can we consider that all languages which are in the arithmetical hierarchy, excluding those in $\Delta$1, refer to an infinite binary sequence considered random by Martin-Löf

1

There are 1 best solutions below

1
On BEST ANSWER

No, not at all.

Let $f$ be any binary sequence whatsoever and let $g(2n)=f(n), g(2n+1)=0$. Then $g$ is not Martin-Lof random but $\{x:g(x)=1\}$ is exactly as complicated as $\{x:f(x)=1\}$. Non-randomness is not a simplicity condition.

Or, put another way, complexity does not imply randomness. (For an extreme type of example of highly-complex but highly-nonrandom sequences, consider genericity.)