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ω to 2ω, extending feedback Turing computation in analogy with the standard notion of computability for functions from 2ω to 2ω. 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 2147 times.
    This article's PDF has been downloaded 303 times.