Generic amplification of recursively enumerable sets (Q1731522)

The generic amplification method was introduced in [\textit{A. G. Myasnikov} and \textit{A. N. Rybalov}, J. Symb. Log. 73, No. 2, 656--673 (2008; Zbl 1140.03025)] in order to obtain generically undecidable sets. Informally, a generically undecidable set is ``undecidable for almost all inputs''. Formally, fix a set \(I\) of all possible inputs. Set \(I\) has a \textit{size function} if there is a function \[ \mathrm{size}:I\rightarrow\mathbb{N} \] such that \(I_n=\{x\in I:\mathrm{size}(x)=n\}\) is a finite set for every \(n\in \mathbb{N}\). For every set \(S\subseteq I\) let \[ \rho_n(S)=\frac{|S\cap I_n|}{|I_n|} \] for every \(n\in\mathbb{N}\). The asymptotic density \(\rho(S)\) of \(S\) is \[ \rho(S)=\lim_{n\rightarrow\infty}\rho_n(S) \] if this limit exists. A set \(S\) is \textit{generic} if \(\rho(S)=1\) and is \textit{negligible} if \(\rho(S)=0\). An algorithm \(\mathcal{A}\) with a set of output \(J\cup\{?\}\), \((?\not\in J)\), is \textit{generic} if and only if \begin{itemize} \item[(1)] \(\mathcal{A}\) halts on all inputs in \(I\), \item[(2)] \(\rho(\{x\in I:\mathcal{A}(x)\not=?\})=1\). \end{itemize} A generic algorithm \(\mathcal{A}\) computes a function \(f:I\rightarrow J\) if \(\mathcal{A}(x)=y\) implies \(f(x)=y\) for all \(x\in I\). A set \(S\subseteq I\) is \textit{generically decidable} if there is a generic algorithm that computes its characteristic function, \textit{generically undecidable} otherwise. A \textit{cloning} of \(I\) in \(J\) is a function \(C\) from \(I\) into the power set \(\mathcal{P}(J)\) such that \(C(x)\cap C(y)=\emptyset\) for every \(x\not=y\). A cloning \(C:I\rightarrow\mathcal{P}(J)\) is \textit{nonnegligible} if the set \(C(x)\) is not negligible in \(J\) for any \(x\in I\). The notion of \textit{generic amplification} is based on the following result in [loc. cit.]: Theorem. Let \(I\) and \(J\) be sets with size functions and let \(C:I\rightarrow\mathcal{P}(J)\) be an effective nonnegligible cloning. If \(S\subseteq I\) is an undecidable set then \[ C(S)=\bigcup_{x\in S}C(x) \] is generically undecidable. A natural question is whether every generically undecidable set can be obtained via the generic amplification method. In the paper under review the author answers negatively to this question, providing as a counterexample a subclass of the class of recursively enumerable sets. Namely: let \(W\subseteq \mathbb{N}\) be a simple negligible set. Then \begin{itemize} \item[(i)] \(W\) is generically undecidable, and \item[(ii)] there does not exist a nonnegligible cloning \(C:\mathbb{N}\rightarrow\mathcal{P}(\mathbb{N})\) such that \(W=C(S)\) for some \(S\subseteq\mathbb{N}\). \end{itemize} On the other hand, it is proven that every recursively enumerable set that has nonzero asymptotic density can be obtained via the generic amplification method from the set \(\mathbb{N}\). Namely: let \(W\subseteq\mathbb{N}\) be any recursively enumerable set with nonzero asymptotic density. Then there exists an effective nonnegligible cloning \(C:\mathbb{N}\rightarrow\mathcal{P}(\mathbb{N})\) for which \(W=C(\mathbb{N})\).