Q Versus QC
William I. Gasarch, Georgia A. Martin · Birkhäuser Boston eBooks · 1999
In this chapter we examine sets A such that (∃ n ≥ l)[Q( n , A ) = QC( n,A )]. Of course, for every set A we have that (∀ n ≥ l)[QC( n , A ) Q( n , A )]. Thus here we are studying sets A such that (∃ n ≥ l )[Q( n , A ) QC( n , A )]. This condition holds of a set A iff there is some n ≥ 1 with the property that, for every set B ∈ Q( n , A ): there is an oracle Turing machine M () for deciding B with n queries to A such that, for all x , X , the M x ( x ) computation converges after making at most n queries to X . This is equivalent to saying that M A decides B with n queries to A and, for every x and every string σ ∈ {0,1} n , the M σ ( x ) computation converges (see Notation 1.2.19)