Speaker
Leonardo Pacheco
TU Wien
Talks at this conference:
Tuesday, 17:20, J431 
Higherorder feedback computation 
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 semicomputable sets are the \(\Pi^1_1\) sets. We can also show that the feedback semicomputable 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 secondorder feedback machines. Note that we must now have a new and stronger notion of freezing to avoid a contradiction by diagonalization. Having defined secondorder feedback computation, it is now natural to ask: what about third, fourth, and higherorder feedback? We define \(\alpha\)th order feedback Turing machines for each computable ordinal \(\alpha\).
We also describe feedback computable and semicomputable sets using inductive definitions and Gale–Stewart games.
Specifically, we prove the following levelbylevel correspondence:
(This is joint work with Juan P. Aguilera and Robert S. Lubarsky.) Bibliography
