Type 1 Computability Type 2 Computability

For any representation δ there is a derived numbering v_δ, defined by ν_δ(i):=δφ_i, of the δ-computable elements. In this chapter the relation between δ-computability and ν_δ-computability is investigated. It is easy to show that the restriction of a (δ,δ,)-computable function to the computable elements is (ν_δ,ν_δ’)-computable. The converse does not seem to be true in general. Only for two special cases a positive answer is known: for “effective” metric spaces (special cases have been proved independently by Ceitin, by Kreisel, Lacombe, and Shoenfield, and by Moschovakis) and for “computable” cpo’s (a special case has been proved by Myhill and Sheperdson). As a corollary we obtain a theorem which characterizes the ν_δ-r.e. subsets of the δ-computable elements for “computable” cpo’s (Rice /Shapiro theorem). The proofs of the main theorems are rather sophisticated.