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
    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 1144 times.
    This article's PDF has been downloaded 234 times.