Feedback computability on Cantor space

zbMATH Open1515.03196arXiv1708.01139MaRDI QIDQ6289745FDOQ6289745

Authors: Nathanael Ackerman, Cameron E. Freer, Robert S. Lubarsky 

Publication date: 3 August 2017

Abstract: We introduce the notion of feedback computable functions from $2^{o}mega$ to $2^{o}mega$, extending feedback Turing computation in analogy with the standard notion of computability for functions from $2^{o}mega$ to $2^{o}mega$. We then show that the feedback computable functions are precisely the effectively Borel functions. With this as motivation we define the notion of a feedback computable function on a structure, independent of any coding of the structure as a real. We show that this notion is absolute, and as an example characterize those functions that are computable from a Gandy ordinal with some finite subset distinguished.

Mathematics Subject Classification ID

Computable structure theory, computable model theory (03C57) Descriptive set theory (03E15) Higher-type and set recursion theory (03D65) Other degrees and reducibilities in computability and recursion theory (03D30)

This page was built for publication: Feedback computability on Cantor space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6289745)