# Higher-order feedback computation

## Leonardo Pacheco

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

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