Ackerman, Nathanael L. and Freer, Cameron E. and Lubarsky, Robert S. - Feedback computability on Cantor space

lmcs:3834 - Logical Methods in Computer Science, April 30, 2019, Volume 15, Issue 2
Feedback computability on Cantor space

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

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.


Source : oai:arXiv.org:1708.01139
Volume: Volume 15, Issue 2
Published on: April 30, 2019
Submitted on: August 4, 2017
Keywords: Mathematics - Logic,Computer Science - Logic in Computer Science,Primary 03D65, Secondary 03C57, 03D30, 03E15


Share