Downey and Hirschfeldt seem to assume that any computably enumerable set of sequences can be generated from some prefix-free set (in the sense that the set of all extensions of the strings in the prefix-free set is equal to the first set). I don't understand why this would be so.

Specifically, in a proof that a sequence is Martin-Löf random iff is there is no c.e. martingale on the sequence that produces infinite profit, on page 236, D&H assume that for each class $U_n$ that makes up a Martin-Löf test, there is a "prefix-free generator" $R_n$ (which I take to be what I described above, cf. p. 4). D&H's definition of Martin-Löf test is on 231: the sequence of $U_n$ is merely required to be uniformly c.e. s.t. $\mu(U_n)\leq 2^{-n}$.

I don't understand why such a generator must always exist.

For example, let $U_n$ be$\{00000\ldots\}$ for all $n$. Then each $U_n$ is null with respect to the uniform measure, so this is a Martin-Löf test. However, any finite sequence of zeros that would include a sequence of all zeros as an extension, would also have extensions such as $01\ldots$, $001\ldots$, etc., which are not in $U_n$. So there is no generator of $U_n$.

Clearly I am misunderstanding something (or have not noticed some constraint on Martin-Löf tests?).


After a lot of thinking and reading, and getting a helpful answer and comments from Andrej Bauer to another question that my investigation prompted, I can answer my own question. I post an answer for the benefit of anyone who may find the question to be similar to one of their own. I expect no upvotes for answering my own question.

Downey and Hirschfeldt prove (2.19.2, p. 74) that every $\Sigma^0_1$ set of infinite sequences is one that can be generated by a c.e. set of finite strings. Moreover, they define Martin-Löf randomness in terms of a sequence of $\Sigma^0_1$ sets $U_n$ of infinite sequences. This is why they have the right to assume that every such $U_n$ can be generated by such a set of finite strings.

In my gloss of D&H's description of a Martin-Löf test, I stated the requirement that the test sets be $\Sigma^0_1$ as a requirement that they be computably enumerable. One can see the equivalence of $\Sigma^0_1$ and c.e. as implied by D&H's proposition 2.19.2, but it's proved directly by, for example, Nies, 1.4.12, p. 22. So the way that I characterized D&H's description of Martin-Löf tests was correct.

While it's true that $U_n=\{000\ldots\}$ can't be generated by finite strings, my mistake was thinking that such a $U_n$ is computably enumerable. It was surprising to me to realize that such a trivially simple set is not c.e. After all, the set has only one element, and a Turing machine that generates it or checks for it is trivial. The crucial point, though, is that that machine cannot halt on $000\ldots$, since the sequence of zeros is infinite. No program can ever successfully list or accept even (the) one member of this set. Thus my sequence of sets $U_n$ do not form a Martin-Löf test.

(It is possible to define a Martin-Löf test that excludes only $000\ldots$ from the random sequences, but that test has to consist of sets such as, for example, $U_n=\{x:$ the first $n$ digits of $x$ are 0$\}$. Each such set contains an uncountably infinite number of infinite sequences, but each is a subset of previous sets $U_1, U_2, \ldots, U_{n-1}$. The one sequence contained in each of them is $000\ldots$ .)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.