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

lmcs:3834 - Logical Methods in Computer Science, April 30, 2019, Volume 15, Issue 2 - https://doi.org/10.23638/LMCS-15(2:7)2019
Feedback computability on Cantor spaceArticle

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

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.


Volume: Volume 15, Issue 2
Secondary volumes: Selected Papers of the 30th and 31st ACM/IEEE Symposium on Logic in Computer Science (LICS 2015 and 2016)
Published on: April 30, 2019
Accepted on: February 6, 2019
Submitted on: August 4, 2017
Keywords: Mathematics - Logic, Computer Science - Logic in Computer Science, Primary 03D65, Secondary 03C57, 03D30, 03E15

Consultation statistics

This page has been seen 3209 times.
This article's PDF has been downloaded 431 times.