Question

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 for itself?

Answer 1

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.

Answer 2

This seems to be very closely related to an old paper of mine, "Complexity of Winning Strategies" (Discrete Math. 3 (1972) 295-300). That paper concerned games that "can really be played" in the sense that the moves are natural numbers (or similar finitary objects), the game is sure to end after finitely many moves, and there is an algorithm to tell, given any position, (1) whether the game has ended, (2) if so, who won, and (3) if not, who is to move next. Because of the finite termination requirement, one of the players has a winning strategy. The main result in the paper is that one of the players has a hyperarithmetical winning strategy and this is optimal, in the sense that, for any hyperarithmetical set $A$, there is a game of this sort such that $A$ is computable from every winning strategy.

The question at hand is not exactly the same, since it's about deciding who wins rather than finding the winning strategy. I strongly suspect, though, that the same method will give the corresponding result --- in fact with a better form of optimality, since "computable from a set decidable from competing provers" simplifies to "decidable from competing provers". I therefore expect that "decidable from competing provers" is equivalent to "hyperarithmetical."

Answer 3

A partial answer is that the class includes all arithmetical sets, as follows. Suppose $S$ is defined by a formula $\psi(n) \equiv (\exists a)(\forall b)(\exists c)(\forall d) \cdots \phi(n, a, b, c, d, ...)$ where $\phi$ is quantifier free. By adding dummy quantifiers we can require that the quantifiers all occur in blocks of two like that, exists followed by forall. A function to decide $S$ from competing provers is as follows. First it asks $Y$ for a value of $a$. Then it asks $N$ for a value of $b$ given $a$. Then it asks $Y$ for a value of $c$ given $a$ and $b$, and so on. Once it has values for all the variables in $\phi$, it checks whether $\phi$ holds with those values plugged in. If so, it accepts $n$, and if not it rejects $n$.

If $n \in S$ then $Y$ has a winning strategy, because $\psi(n)$ is true. All $Y$ has to do is pick appropriate values for each existential quantifier, which have to exist if $\psi(n)$ holds. Otherwise, $\lnot \psi(n)$ is true, so $N$ has a winning strategy using the same technique of picking witnesses for the existential quantifiers in $\lnot \psi$.

Not every set in $S$ is arithmetical, though. As usual let $0^{a}$ be the $a$-th iterated Turing jump of the empty set. Consider $$S = 0^{(\omega)} = \{ 2^a3^b : b \in 0^{a}\}.$$ This is not an arithmetical set, but it can be accepted from competing provers as follows. First the machine looks at the input $n$ and decodes it into $2^a3^b$. If the number is not of that form the machine can just reject out of hand. If it is of that form, the machine pretends that it was given input $b$ and checks whether that number is in $0^{a}$ using $Y$ and $N$. Because an arithmetical formula for $0^{a}$ is uniformly recoverable from $a$, this can be done effectively, and $Y$ and $N$ will have the appropriate strategies because $0^{a}$ is arithmetical.

Note all the machines in this answer so far will halt on all strategies, and in fact we can give a bound on how many queries the machine will make as a function of $n$.

Answer 4

In computational complexity theory, the polynomial-time version of your class is known as $S_2P$. For a brief description, see here: http://qwiki.stanford.edu/index.php/Complexity_Zoo_1.0#s2p

It occurs in a few interesting complexity theorems.