Recursion theoretic properties of frequency computation and bounded queries (Q1898479)

A set \(A\) is called \((m,n)\)-recursive (in short \(A \in \Omega (m,n))\) if there is a recursive function \(f : \omega^n \to \{0,1\}^n\) such that for all pairwise distinct numbers \(x_1, x_2, \dots, x_n\), \[ f(x_1, x_2, \dots, x_n) = (b_1, b_2, \dots, b_n) \Rightarrow \biggl |\bigl \{i : \chi_A (x_i) = b_i \bigr\} \biggr |\geq m. \] \(A\) is strongly \((m,n)\)-verbose (in short \(A \in V_s (m,n))\) if there is a recursive function \(f\) such that for all \(x_1, x_2, \dots, x_n\), \[ |D_{f (x_1, x_2, \dots, x_n)} |\leq m \;\&\;\bigl \langle \chi_A (x_1), \chi_A (x_2), \dots, \chi_A (x_n) \bigr \rangle \in D_{f (x_1, x_2, \dots, x_n)}, \] where \(D_i\) is the \(i\)-th finite set in a canonical indexing of all finite sets. It is not difficult to see that \(\bigcup_{n \geq 1, 1 \leq m \leq n} \Omega (m,n) = \bigcup_{n \geq 1, m < 2^n} V_s (m,n)\). This class is denoted by \(\Omega\). The inclusion relations among the \(V_s (m,n)\)-classes and \(\Omega (m,n)\)-classes have been discussed by \textit{R. Beigel} and the authors [Inf. Comput. 118, No. 1, 73-90 (1995; Zbl 0827.68082)], \textit{A. M. Dëgtev} [Algebraic systems, Interuniv. Collect. Sci. Works, Ivanovo 1981, 88-99 (1981; Zbl 0536.03022)] and the authors [``Some aspects of frequency computation'', Techn. Rep. Nr. 21/91, Fak. Informatik, Univ. Karlsruhe]. This paper discusses widely the recursion-theoretic properties of the class \(\Omega\). In particular, it is shown how well-known properties of r.e. sets as simplicity and completeness are related to frequency computation and verboseness. For example, it is shown that: There is a simple non-hypersimple set \(A\) which is in \(\Omega (n,2n + 1) \cap V_s (1 + (n (n + 1)/2), n)\) (Theorem 4.3); If \(A\) is simple and \(A \in V_s ((n(n + 1)/2), n)\) for some \(n > 0\), then \(A\) is hypersimple but not hyperhypersimple (Theorem 4.7); The sets in \(\Omega\) cannot be \(m\)- complete (Fact 5.1), btt-complete (Theorem 5.2) or \(d\)-complete (Theorem 5.3); There is no \(c\)-complete set in \(\Omega (n,2n)\) or \(V_s (n(n + 1)/2, n)\) (Theorem 5.4); But there is a \(c\)-complete set in \(\Omega (2,2n + 1) \cap V_s (1 + (n(n + 1)/2), n)\) for all \(n > 0\) (Theorem 5.5); etc. A comprehensive summary about the related known results is also given at the end of the paper.