Self-Specifying Machines
<|reference_start|>Self-Specifying Machines: We study the computational power of machines that specify their own acceptance types, and show that they accept exactly the languages that $\manyonesharp$-reduce to NP sets. A natural variant accepts exactly the languages that $\manyonesharp$-reduce to P sets. We show that these two classes coincide if and only if $\psone = \psnnoplusbigohone$, where the latter class denotes the sets acceptable via at most one question to $\sharpp$ followed by at most a constant number of questions to $\np$.<|reference_end|>
@article{hemaspaandra1999self-specifying,
    title={Self-Specifying Machines},
    author={Lane A. Hemaspaandra, Harald Hempel, and Gerd Wechsung},
    journal={arXiv preprint arXiv:cs/9910006},
    year={1999},
    number={earlier version appears as UR-CS-TR-97-654},
    archivePrefix={arXiv},
    eprint={cs/9910006},
    primaryClass={cs.CC}
}