SELF-SPECIFYING MACHINES
Lane A. Hemaspaandra, Harald Hempel⋆, Gerd Wechsung · International Journal of Foundations of Computer Science · 1999
We study the computational power of machines that specify their own acceptance types, and show that they accept exactly the languages that [Formula: see text]-reduce to NP sets. A natural variant accepts exactly the languages that [Formula: see text]-reduce to P sets. We show that these two classes coincide if and only if [Formula: see text], where the latter class denotes the sets acceptable via at most one question to #P followed by at most a constant number of questions to NP.