Feedback computability on Cantor space Article Swipe
Related Concepts
Nathanael Ackerman
,
Cameron E. Freer
,
Robert S. Lubarsky
·
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.23638/lmcs-15(2:7)2019
· OA: W2744104426
YOU?
·
· 2019
· Open Access
·
· DOI: https://doi.org/10.23638/lmcs-15(2:7)2019
· OA: W2744104426
We introduce the notion of feedback computable functions from $2^\omega$ to $2^\omega$, extending feedback Turing computation in analogy with the standard notion of computability for functions from $2^\omega$ to $2^\omega$. 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.
Related Topics
Finding more related topics…