4
$\begingroup$

Let $K(x)$ denote the Kolmogorov complexity of a finite binary string $x$. A finite binary string $x$ is called Kolmogorov random if $K(x) \geq |x|$. And an infinite binary sequence is called Martin-Löf random if there exists a natural number $c$ such that every finite prefix $x$ of the sequence satisfies $K(x) \geq |x| - c$.

Now the set of Kolmogorov random finite binary strings, viewed as a set of natural numbers, is an immune set, i.e. it contains no infinite recursively enumerable subsets. The set of Martin-Löf random infinite binary sequences, being uncountable, obviously cannot be viewed as a set of natural numbers. But my question is, is there some notion analogous to immunenesss which applies to the set of Martin-Löf random infinite binary sequences?

Effective descriptive set theory seems relevant, since descriptive set theory studies the properties of sets of real numbers, and effective descriptive set theory in particular studies computability-related properties of sets of real numbers.

$\endgroup$

1 Answer 1

1
$\begingroup$

In DST, the analogue would be having empty interior. The generalization of r.e. sets to the Polish setting is $\Sigma^0_1$ sets, which are recursively enumerable unions of open sets in our effective basis. The natural polish space here is $2^\omega$ since we're considering sets of naturals. The set of infinite binary strings that are eventually $0$ are dense in Cantor space, and all non-random. Thus the set of Martin-Löf random strings has empty interior.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .