Abstract

If S is a finite set, let |S| be the cardinality of S. We show that if $m \in \omega, A \subseteq \omega, B \subseteq \omega$ , and |{i: 1 ≤ i ≤ 2 m & x i ∈ A}| can be computed by an algorithm which, for all x 1 ,...,x 2 m , makes at most m queries to B, then A is recursive in the halting set K. If m = 1, we show that A is recursive