Defining the degree of categoricity of a computable structure ${\mathcal{M}}$ to be the least degree d for which ${\mathcal{M}}$ is d-computably categorical, we investigate which Turing degrees can be realized as degrees of categoricity. We show that for all n, degrees d.c.e. in and above 0 (n) can be so realized, as can the degree 0 (ω).

We obtain a large class of significant examples of n-random reals (i.e., Martin-Löf random in oracle $\varphi ^{(n - 1)} $ ) à la Chaitin. Any such real is defined as the probability that a universal monotone Turing machine performing possibly infinite computations on infinite (resp. finite large enough, resp. finite self-delimited) inputs produces an output in a given set O ⊆(ℕ). In particular, we develop methods to transfer $\Sigma _n^0 $ or $\Pi _n^0 $ or many-one completeness results of (...) index sets to n-randomness of associated probabilities. (shrink)

§1. Iterated Gödelian extensions of theories. The idea of iterating ad infinitum the operation of extending a theory T by adding as a new axiom a Gödel sentence for T, or equivalently a formalization of “T is consistent”, thus obtaining an infinite sequence of theories, arose naturally when Godel's incompleteness theorem first appeared, and occurs today to many non-specialists when they ponder the theorem. In the logical literature this idea has been thoroughly explored through two main approaches. One is that (...) initiated by Turing in his “ordinal logics” and taken very much further in Feferman's work on transfinite progressions, which also introduced the more general study of extensions by reflection principles, of which consistency statements are a special case. This approach starts from an assignment of theories to ordinal notations, and extracts sequences of theories through a suitable choice of a path in the set of ordinal notations. The second approach, illustrated in particular by the work of Schmerl and Beklemishev, starts instead from a suitably well-behaved primitive recursive well-ordering, which is used to define a sequence of theories. This second approach has led to precise results about the relative proof-theoretical strength of sequences of theories obtained by iterating different reflection principles. The Turing-Feferman approach, on the other hand, lends itself well to an investigation in qualitative and philosophical terms of the relevance of such iterated reflection extensions to mathematical knowledge, in particular because of two developments associated with this approach. (shrink)

Kleene [5] mentions two ways of extending the constructive ordinals. The first is by relativizing the setOof notations for the constructive ordinals, using fundamental sequences which are partial recursive inO. In this way we obtain the setOOwhich provides notations for the ordinals less than ω1O. Continuing the process, the sequenceO,OO,, … and the corresponding ordinalsare obtained. A second possibility is to define higher number classes in which partial recursive functions are used at limit ordinals to provide an “accessibility” mapping from (...) a previously defined number class. The relationship between the ordinals obtained by the two methods of extension has been an open problem. Methods developed in this article are used to show that the two ways of extending the constructive ordinals are equivalent, provided the sets of notations for the higher number classes satisfy certain natural conditions. Equivalence is obtained, not only with respect to ordinals, but also with respect to the forms of the sets of notations for the higher number classes. Specifically, the fundamental fact that the sets of notations for the constructive ordinals are complete Π11sets generalizes to suitably defined higher number classes. As an application we prove that the ordinals of the Addison and Kleene [1] constructive third number class are exactly the ordinals less than ω1Oand the setof notations for their third number class is recursively isomorphic toOO. (shrink)