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<T b 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.