pith. sign in

arxiv: 1708.01139 · v5 · pith:MZPAHXINnew · submitted 2017-08-03 · 🧮 math.LO · cs.LO

Feedback computability on Cantor space

classification 🧮 math.LO cs.LO
keywords feedbackfunctionscomputablenotionomegacomputabilitystructureabsolute
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.