Degrees of Unsolvability of Continuous Functions

Journal of Symbolic Logic 69 (2):555 - 584 (2004)
We show that the Turing degrees are not sufficient to measure the complexity of continuous functions on [0, 1]. Computability of continuous real functions is a standard notion from computable analysis. However, no satisfactory theory of degrees of continuous functions exists. We introduce the continuous degrees and prove that they are a proper extension of the Turing degrees and a proper substructure of the enumeration degrees. Call continuous degrees which are not Turing degrees non-total. Several fundamental results are proved: a continuous function with non-total degree has no least degree representation, settling a question asked by Pour-El and Lempp; every non-computable f $\epsilon \mathcal{C}[0, 1]$ computes a non-computable subset of $\mathbb{N}$ ; there is a non-total degree between Turing degrees $a _\eqslantless_{\tau}$ b iff b is a PA degree relative to a; $\mathcal{S} \subseteq 2^{\mathbb{N}}$ is a Scott set iff it is the collection of f-computable subsets of $\mathbb{N}$ for some f $\epsilon \mathcal{C}[O, 1]$ of non-total degree; and there are computably incomparable f, g $\epsilon \mathcal{C}[0, 1]$ which compute exactly the same subsets of $\mathbb{N}$ . Proofs draw from classical analysis and constructive analysis as well as from computability theory
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.2178/jsl/1082418543
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 24,479
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
Alan L. Selman (1971). Arithmetical Reducibilities I. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 17 (1):335-350.
Alan L. Selman (1971). Arithmetical Reducibilities I. Mathematical Logic Quarterly 17 (1):335-350.

Add more references

Citations of this work BETA
Jan Reimann (2008). Effectively Closed Sets of Measures and Randomness. Annals of Pure and Applied Logic 156 (1):170-182.

Add more citations

Similar books and articles
Peter G. Hinman (1973). Degrees of Continuous Functionals. Journal of Symbolic Logic 38 (3):393-395.
Guohua Wu (2004). Bi-Isolation in the D.C.E. Degrees. Journal of Symbolic Logic 69 (2):409 - 420.
Stephen G. Simpson (2005). Mass Problems and Randomness. Bulletin of Symbolic Logic 11 (1):1-27.
Michael Stob (1983). Wtt-Degrees and T-Degrees of R.E. Sets. Journal of Symbolic Logic 48 (4):921-930.
Guohua Wu (2006). Jump Operator and Yates Degrees. Journal of Symbolic Logic 71 (1):252 - 264.
Harold T. Hodes (1982). Jumping to a Uniform Upper Bound. Proceedings of the American Mathematical Society 85 (4):600-602.

Monthly downloads

Added to index


Total downloads

13 ( #333,351 of 1,925,766 )

Recent downloads (6 months)

1 ( #418,414 of 1,925,766 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.