Degrees of unsolvability of continuous functions
- 1 June 2004
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 69 (2) , 555-584
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 ∈ [0,1] computes a non-computable subset of ℕ there is a non-total degree between Turing degrees a <Tb iff b is a PA degree relative to a; ⊆ 2ℕ is a Scott set iff it is the collection of f-computable subsets of ℕ for some f ∈ [0,1] of non-total degree; and there are computably incomparable f, g ∈ [0,1] which compute exactly the same subsets of ℕ. Proofs draw from classical analysis and constructive analysis as well as from computability theory.Keywords
This publication has 22 references indexed in Scilit:
- ∏10 Classes in Computability Theory1999
- Definability in the enumeration degreesArchive for Mathematical Logic, 1997
- Computability on computable metric spacesTheoretical Computer Science, 1993
- Computability and noncomputability in classical analysisTransactions of the American Mathematical Society, 1983
- First-Order Theory of the Degrees of Recursive UnsolvabilityAnnals of Mathematics, 1977
- Arithmetical Reducibilities IMathematical Logic Quarterly, 1971
- The Recursively Enumerable Degrees are DenseAnnals of Mathematics, 1964
- On Degrees of Recursive UnsolvabilityAnnals of Mathematics, 1956
- Fixed Point Theorems for Multi-Valued TransformationsAmerican Journal of Mathematics, 1946
- Invariant points in function spaceTransactions of the American Mathematical Society, 1922