Degrees of Unsolvability of Continuous Functions

Journal of Symbolic Logic 69 (2):555 - 584 (2004)
  Copy   BIBTEX

Abstract

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,168

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Maximal contiguous degrees.Peter Cholak, Rod Downey & Stephen Walk - 2002 - Journal of Symbolic Logic 67 (1):409-437.
Degrees of continuous functionals.Peter G. Hinman - 1973 - Journal of Symbolic Logic 38 (3):393-395.
Weak Presentations of Computable Fields.Carl G. Jockusch & Alexandra Shlapentokh - 1995 - Journal of Symbolic Logic 60 (1):199 - 208.
Bi-Isolation in the D.C.E. Degrees.Guohua Wu - 2004 - Journal of Symbolic Logic 69 (2):409 - 420.
Mass problems and randomness.Stephen G. Simpson - 2005 - Bulletin of Symbolic Logic 11 (1):1-27.
Wtt-degrees and t-degrees of R.e. Sets.Michael Stob - 1983 - Journal of Symbolic Logic 48 (4):921-930.
Jump Operator and Yates Degrees.Guohua Wu - 2006 - Journal of Symbolic Logic 71 (1):252 - 264.
Jumping to a Uniform Upper Bound.Harold T. Hodes - 1982 - Proceedings of the American Mathematical Society 85 (4):600-602.
A hierarchy for the plus cupping Turing degrees.Yong Wang & Angsheng Li - 2003 - Journal of Symbolic Logic 68 (3):972-988.
A model with no magic set.Krzysztof Ciesielski & Saharon Shelah - 1999 - Journal of Symbolic Logic 64 (4):1467-1490.
Complementation in the Turing degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
On the structures inside truth-table degrees.Frank Stephan - 2001 - Journal of Symbolic Logic 66 (2):731-770.

Analytics

Added to PP
2010-08-24

Downloads
24 (#482,878)

6 months
1 (#448,551)

Historical graph of downloads
How can I increase my downloads?

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
Introduction to Metamathematics.H. Rasiowa - 1954 - Journal of Symbolic Logic 19 (3):215-216.
Arithmetical Reducibilities I.Alan L. Selman - 1971 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 17 (1):335-350.
Arithmetical Reducibilities I.Alan L. Selman - 1971 - Mathematical Logic Quarterly 17 (1):335-350.

View all 8 references / Add more references