Feedback computability on Cantor space

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 effect...

Full description

Saved in:
Bibliographic Details
Published in:Logical methods in computer science 2019-01, Vol.15, Issue 2
Main Authors: Nathanael L. Ackerman, Cameron E. Freer, Robert S. Lubarsky
Format: Article
Language:English
Subjects:
computer science - logic in computer science
mathematics - logic
primary 03d65, secondary 03c57, 03d30, 03e15
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1860-5974
DOI:10.23638/LMCS-15(2:7)2019