Let $n$ be a member of $\omega$, which the omnipotent provers $Y$ and $N$ know. A Turing machine will be run starting with the $n$ already inputted, and the machine can have a natural number inputted from the prover of its choice, with no limit on the number of times it can do so.
  
  
  

Let $S$ be a subset of $\omega$.
  
  

Definition: S is decidable from competing provers if and only if
  
  

there exists a Turing machine such that, for all members $n$ of $\omega$, when run as above,
  

(1) if $n\in S$ then $Y$ has a strategy that will force the Turing machine to accept
  

(0) else $N$ has a strategy that will force the Turing machine to reject
  
  
  
  

What subsets $S$ of $\omega$ are decidable from competing provers?
  

What if the Turing machine is required to always halt?
  

In each case, is the resulting class [low](http://en.wikipedia.org/wiki/Low_%28complexity%29) for itself?



What sets are "decidable from competing provers"?
The result I expected in my previous answer turns out to be correct and somewhat easier than the old paper that led me to expect it. Here's a proof that "decidable from competing provers" is equivalent to "hyperarithmetical."


Suppose first that $S$ is decidable from competing provers, and fix a Turing machine $M$ as in the statement of the problem. Then a natural number $n$ is in $S$ if and only if there is a strategy $s$ for player $Y$ such that, for no *finite* sequence $p$ of moves of $N$ does the machine $M$ reject after $N$ has played $p$ (without asking for any further inputs from $N$). Because we need only consider finite plays by $N$, and because the operation of a Turing machine can be described arithmetically, this characterization of $n\in S$ involves only one quantifier that goes beyond arithmetic, namely "there exists a strategy $s$"; that's one existential quantifier over (what amounts to) reals, so $S$ is a $\Sigma^1\_1$ set. A symmetrical argument shows that the complement of $S$ is also $\Sigma^1\_1$, and therefore $S$ is hyperarithmetical.


For the converse, let $S$ be any hyperarithmetical set, and fix $\Sigma^1\_1$ definitions, in normal form, for both $S$ and its complement. So we have recursive predicates $P$ and $Q$ such that, for all $n$,


* $n\in S$ iff there is a function $f:\mathbb N\to\mathbb N$ such that, for all $k\in\mathbb N$ the restriction $\bar f(k):=f\upharpoonright\{0,\dots,k-1\}$ satisfies $P(n,\bar f(k))$, and
* $n\notin S$ iff there is $g:\mathbb N\to\mathbb N$ such that, for all $k\in\mathbb N$ we have $Q(n,\bar g(k))$.


Let $M$ be the Turing machine that, given input $n$, alternately asks $Y$ and $N$ for natural numbers, interpreting $Y$'s (resp. $N$'s) inputs as successive values of $f$ (resp. $g$). After each value is received, the machine checks whether $P$ (resp. $Q$) holds of $n$ and the sequence of values of $f$ (resp. $g$) received so far. They can't both continue to hold forever, since that would put $n$ into both $S$ and its complement. As soon as a failure occurs, $M$ says that $n$ is not (resp. is) in $S$ if $P$ (resp. $Q$) failed first. Now if in fact $n\in S$, then $Y$ can give $M$ the values of an appropriate witness $f$ so that $P$ will never fail. Therefore $Q$ will eventually fail (no matter what $N$ does), and $M$ will correctly decide that $n\in S$. Symmetrically, if $n\notin S$, then $N$ can make $M$ say so, by playing a witness $g$. Therefore, $M$ decides $S$ from competing provers.


