Feedback Turing machines are Turing machines which can query a halting oracle \(h:\subseteq \omega\times\omega\to \{\downarrow,\uparrow\}\), which has information on the convergence or divergence of feedback computations. That is, given the code \(e\) for a feedback Turing machine and an input \(n\) the oracle \(h\) answers if the computation \(\{e\}^h(n)\) converges or diverges. To avoid a contradiction by diagonalization, feedback Turing machines have two ways of not converging: they can diverge as standard Turing machines, or they can freeze. A feedback Turing machine freezes when it asks the halting oracle \(h\) about a pair \(\langle{e,n}\rangle\) not in the domain of \(h\).

Feedback Turing machines were first studied by Ackerman, Freer and Lubarsky [1,2]. They proved that the feedback computable sets are the \(\Delta^1_1\) sets and the feedback semi-computable sets are the \(\Pi^1_1\) sets. We can also show that the feedback semi-computable sets are the winning regions of Gale–Stewart games with \(\Sigma^0_1\) payoff [3].

A natural question to ask is: what about feedback Turing machines which can ask if computations of the same type converge, diverge, or freeze? These new machines are second-order feedback machines. Note that we must now have a new and stronger notion of freezing to avoid a contradiction by diagonalization. Having defined second-order feedback computation, it is now natural to ask: what about third-, fourth-, and higher-order feedback?

We define \(\alpha\)th order feedback Turing machines for each computable ordinal \(\alpha\). We also describe feedback computable and semi-computable sets using inductive definitions and Gale–Stewart games. Specifically, we prove the following level-by-level correspondence:
Theorem. For all \(\alpha<\omega_1^\mathrm{ck}\), the following classes coincide:

• the \((\alpha+1)\)-feedback semi-computable sets;
• the sets definable by \(\alpha+1\) simultaneous arithmetical inductive operators; and
• the sets of winning positions of Gale–Stewart games whose payoffs are differences of \(\alpha+1\) many \(\Sigma^0_2\) sets.

(This is joint work with Juan P. Aguilera and Robert S. Lubarsky.)

Bibliography

1. Nathanael L. Ackerman and Cameron E. Freer and Robert S. Lubarsky,Feedback Turing Computability, and Turing Computability as Feedback,30th Annual ACM/IEEE Symposium on Logic in Computer Science,(2015) pp. 523–534.
2. Nathanael L. Ackerman and Cameron E. Freer and Robert S. Lubarsky,An Introduction to Feedback Turing Computability,Journal of Logic and Computation,vol. 30 (2020), no. 1, pp. 27–60.
3. Yannis N. Moschovakis,Descriptive Set Theory,Mathematical surveys and monographs, vol. 155,American Mathematical Society,2009.