Can any computably enumerable set be generated by a prefix-free set?
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?).
turing-machines computability
MarsMars
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$ .)
Not the answer you're looking for? Browse other questions tagged turing-machines computability or ask your own question.
Are all $\Sigma^0_1$ sets of infinite sequences infinite?
Can the encodings set of a non-trivial class of languages which contains the empty set be recursively enumerable?
Constructible enumerable set
A new definition of recursively enumerable set?
Are there any countable sets that are not computably enumerable?
Which one of these two sets is computably enumerable?
Why assume Turing machine can compute arbitrary results in Kraft-Chaitin theorem?
Proof that languages are Turing-recognizable iff computably-enumerable
Undecidability of "is this CFG prefix-free?"