patternMinor
Can any computably enumerable set be generated by a prefix-free set?
Viewed 0 times
computablycangeneratedfreeanyenumerableprefixset
Problem
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?).
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?).
Solution
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.
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$ .)
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$ .)
Context
StackExchange Computer Science Q#131509, answer score: 2
Revisions (0)
No revisions yet.