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,30th Annual ACM/IEEE Symposium on Logic in Computer Science,(2015) pp. 523–534.
- 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.
- Yannis N. Moschovakis,Descriptive Set Theory,Mathematical surveys and monographs, vol. 155,American Mathematical Society,2009.