We study notions of generic and coarse computability in the context of computable structure theory. Our notions are stratified by the Σβ hierarchy. We focus on linear orderings. We show that at the Σ1 level, all linear orderings have both generically and coarsely computable copies. This behavior changes abruptly at higher levels; we show that at the Σα+2 level for any α∈ω1CK the set of linear orderings with generically or coarsely computable copies is Σ11-complete and therefore maximally complicated. This development is new even in the general analysis of generic and coarse computability of countable structures. In the process of proving these results, we introduce new tools for understanding generically and coarsely computable structures. We are able to give a purely structural statement that is equivalent to having a generically computable copy and show that every relational structure with only finitely many relations has coarsely and generically computable copies at the lowest level of the hierarchy.

Abstract In recent years, computability theorists have extensively studied generically and coarsely computable sets. This study of approximate computability was originally motivated by asymptotic density problems in combinatorial group theory. We generalize the notions of generic and coarse computability of sets, introduced by Jockusch and Schupp, to arbitrary structures by defining generically and coarsely computable and computably enumerable structures. There are two directions in which these notions could potentially trivialize: either all structures could have a densely computable copy or only those having a computable (or computably enumerable) copy. We show that some particular classes of structures realize each of these extremal conditions, while other classes realize neither of them. To further explore these concepts, we introduce a graded family of elementarity conditions for substructures, in which we require that the dense sets under consideration be ‘strong’ substructures of the original structure. Here, again, for a given class, the notion could trivialize in the same two directions and we show that both are possible. For each class that we investigate, there is some natural number $n$ such that requiring $\varSigma _{n}$ elementarity of substructures is enough to trivialize the class of generically or densely computable structures, witnessing the essentially structural character of these notions.

Abstract An injection structure ${{\mathcal {A}}} = (A,f)$ is a set $A$ together with a one-place one-to-one function $f$. ${{\mathcal {A}}}$ is a Finite State Transducer (abbreviated FST) injection structure if $A$ is a regular set, i.e. the set of words accepted by some finite automaton, and $f$ is realized by a deterministic FST. We study the complexity of the character of an FST injection structure. We examine the effective categoricity of such structures. We show that the isomorphism problem for unary FST structures is decidable in quadratic time.

Abstract We study the recognition problem in the metaprogramming of finite normal predicate logic programs. That is, let $\mathcal{L}$ be a computable first-order predicate language with infinitely many constant symbols and infinitely many $n$-ary predicate symbols and $n$-ary functions symbols for all $n \geq 1$. Then we can effectively list all the finite normal predicate logic programs $Q_0,Q_1,\ldots $ over $\mathcal{L}$. Given some property $\mathcal{P}$ of finite normal predicate logic programs over $\mathcal{L}$, we define the index set $I_{\mathcal{P}}$ to be the set of indices $e$ such that $Q_e$ has property $\mathcal{P}$. We classify the complexity of the index set $I_{\mathcal{P}}$ within the arithmetic hierarchy for various natural properties of finite predicate logic programs. For example, we determine the complexity of the index sets relative to all finite predicate logic programs and relative to certain special classes of finite predicate logic programs of properties such as (i) having no stable models, (ii) having no recursive stable models, (iii) having at least one stable model, (iv) having at least one recursive stable model, (v) having exactly $c$ stable models for any given positive integer $c$, (vi) having exactly $c$ recursive stable models for any given positive integer $c$, (vii) having only finitely many stable models, (viii) having only finitely many recursive stable models, (ix) having infinitely many stable models and (x) having infinitely many recursive stable models.

Consider a universal oracle Turing machine that prints a finite or an infinite binary sequence, based on the answers to the binary queries that it makes during the computation. We study the probability that this output is infinite and computable when the machine is given a random (in the probabilistic sense) stream of bits as the answers to its queries during an infinitary computation. Surprisingly, we find that these probabilities are the entire class of real numbers in (0,1) that can be written as the difference of two halting probabilities relative to the halting problem. In particular, there are universal Turing machines that produce a computable infinite output with probability exactly 1/2. Our results contrast a large array of facts (the most well-known being the randomness of Chaitin’s halting probability) that witness maximal initial segment complexity of probabilities associated with universal machines. Our proof uses recent advances in algorithmic randomness.

We investigate computability-theoretic properties of computable structures with single unary functions f such that, for every x in the image, f−1(x) has exactly two elements, which we call 2:1 structures. We also investigate structures for which f−1(x) has either exactly two or zero elements, which we call (2,0):1 structures. In particular, we are interested in the complexity of isomorphisms between these structures. We prove that a computable 2:1 structure A is computably categorical if and only if A has only finitely many ℤ-chains. We show that every computable 2:1 structure is Δ20-categorical. We further investigate computable and higher level categoricity of various natural subclasses of (2,0):1 structures, including highly computable and locally finite strufctures.

We investigate the connection between measure and capacity for the space of nonempty closed subsets of {0,1}*. For any computable measure, a computable capacity T may be defined by letting T(Q) be the measure of the family of closed sets which have nonempty intersection with Q. We prove an effective version of Choquet's capacity theorem by showing that every computable capacity may be obtained from a computable measure in this way. We establish conditions that characterize when the capacity of a random closed set equals zero or is >0. We construct for certain measures an effectively closed set with positive capacity and with Lebesgue measure zero.

Abstract We examine the effective categoricity of equivalence structures via Ershov's difference hierarchy. We explore various kinds of categoricity available by distinguishing three different notions of isomorphism available in this hierarchy. We prove several results relating our notions of categoricity to computable equivalence relations: for example, we show that, for such relations, computable categoricity is equivalent to our notion of weak ω-c.e. categoricity, and that -categoricity is equivalent to our notion of graph-ω-c.e. categoricity.

We investigate the notion of K-triviality for closed sets and continuous functions in 2ℕ. For every K-trivial degree d, there exists a closed set of degree d and a continuous function of degree d. Every K-trivial closed set contains a K-trivial real. There exists a K-trivial Π10 class with no computable elements. A closed set is K-trivial if and only if it is the set of zeroes of some K-trivial continuous function. We give a density result for the Medvedev degrees of K-trivial Π10 sets. If W ≤TA′, then W can compute a path through every A′-decidable random closed set if and only if W ≡TA′.

For a pseudojump VX and a Π10 class P, we consider properties of the set {VX:X ∈ P}.We show that if P is Medvedev complete or if P has positive measure, and Ø′ ≤T C, then there exists X ∈ P with VX ≡T C. We examine the consequences when VX is Turing incomparable with VY for X ≠ Y in P and when WeX=WeY for all X, Y ∈ P. Finally, we give a characterization of the jump in terms of Π10 classes.

We investigate notions of randomness in the space C[2 N] of nonempty closed subsets of {0, 1} N. A probability measure is given and a version of the Martin-Löf test for randomness is defined. Π 0 2 random closed sets exist but there are no random Π 0 1 closed sets. It is shown that any random 4 closed set is perfect, has measure 0, and has box dimension log2. A 3 random closed set has no n-c.e. elements. A closed subset of 2 N may be defined as the set of infinite paths through a tree and so the problem of compressibility of trees is explored. If Tn = T ∩ {0, 1} n, then for any random closed set [T] where T has no dead ends, K(Tn) ≥ n − O(1) but for any k, K(Tn) ≤ 2 n−k + O(1), where K(σ) is the prefix-free complexity of σ ∈ {0, 1} ∗. 1

Abstract We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension when length is measured relative to the binary representation of natural numbers and formulas. It is well known that a propositional theory is axiomatizable (respectively decidable) if and only if it may be represented as the set of infinite paths through a computable tree (respectively a computable tree with no dead ends). We show that any polynomial time decidable theory may be represented as the set of paths through a polynomial time decidable tree. On the other hand, the statement that every polynomial time decidable tree represents the set of complete consistent extensions of some theory which is polynomial time decidable, relative to the tally representation of natural numbers and formulas, is equivalent to P = NP. For predicate logic, we develop a complexity theoretic version of the Henkin construction to prove a complexity theoretic version of the Completeness Theorem. Our results imply that that any polynomial space decidable theory Δ possesses a polynomial space computable model which is exponential space decidable and thus Δ has an exponential space complete consistent extension. Similar results are obtained for other notions of complexity.

We study the complexity of computable and -definitions that are computable. We also examine the complexity of a new type of inductive definition, which we call weakly finitary monotone inductive definitions. Applications are given in proof theory and in logic programming.

Abstract. We show that in the lattice of classes there are initial segments [∅, P] = (P) which are not Boolean algebras, but which have a decidable theory. In fact, we will construct for any finite distributive lattice L which satisfies the dual of the usual reduction property a class P such that L is isomorphic to the lattice (P)*, which is (P). modulo finite differences. For the 2-element lattice, we obtain a minimal class, first constructed by Cenzer, Downey, Jockusch and Shore in 1993. For the simplest new class P constructed, P has a single, non-computable limit point and (P)* has three elements, corresponding to ∅, P and a minimal class P0 ⊂ P, The element corresponding to P0 has no complement in the lattice. On the other hand, the theory of (P) is shown to be decidable. A class P is said to be decidable if it is the set of paths through a computable tree with no dead ends. We show that if P is decidable and has only finitely many limit points, then (P)* is always a Boolean algebra. We show that if P is a decidable class and (P) is not a Boolean algebra, then the theory of (P) interprets the theory of arithmetic and is therefore undecidable.

In many areas of scientific inquiry, the phenomena under investigation are viewed as functions on the

Abstract This paper continues joint work of the authors with P. Clote, R. Soare and S. Wainer (Annals of Pure and Applied Logic, vol. 31 (1986), pp. 145–163). An element x of the Cantor space 2ω is said have rank α in the closed set P if x is in Dα(P)/Dα + 1(P), where Dα is the iterated Cantor-Bendixson derivative. The rank of x is defined to be the least α such that x has rank a in some set. The main result of the five-author paper is that for any recursive ordinal λ + n (where λ is a limit and n is finite), there is a point with rank λ + n which is Turing equivalent to O(λ + 2n) All ranked points constructed in that paper are singletons. We now construct a ranked point which is not a singleton. In the previous paper the points of high rank were also of high hyperarithmetic degree. We now construct points with arbitrarily high rank. We also show that every nonrecursive RE point is Turing equivalent to an RE point of rank one and that every nonrecursive point is Turing equivalent to a hyperimmune point of rank one. We relate Clote's notion of the height of a singleton in the Baire space with the notion of rank. Finally, we show that every hyperimmune point x is Turing equivalent to a point which is not ranked.

Abstract Let A and B be subsets of the space 2N of sets of natural numbers. A is said to be Wadge reducible to B if there is a continuous map Φ from 2N into 2N such that A = Φ−1 (B); A is said to be monotone reducible to B if in addition the map Φ is monotone, that is, a ⊂ b implies Φ(a) ⊂ Φ(b). The set A is said to be monotone if a ∈ A and a ⊂ b imply b ∈ A. For monotone sets, it is shown that, as for Wadge reducibility, sets low in the arithmetical hierarchy are nicely ordered. The sets are all reducible to the ( but not ) sets, which are in turn all reducible to the strictly sets, which are all in turn reducible to the strictly sets. In addition, the nontrivial sets all have the same degree for n ≤ 2. For Wadge reducibility, these results extend throughout the Borel hierarchy. In contrast, we give two natural strictly monotone sets which have different monotone degrees. We show that every monotone set is actually positive. We also consider reducibility for subsets of the space of compact subsets of 2N. This leads to the result that the finitely iterated Cantor-Bendixson derivative Dn is a Borel map of class exactly 2n, which answers a question of Kuratowski.

Monotone inductive definitions occur frequently throughout mathematical logic. The set of formulas in a given language and the set of consequences of a given axiom system are examples of (monotone) inductively defined sets. The class of Borel subsets of the continuum can be given by a monotone inductive definition. Kleene's inductive definition of recursion in a higher type functional (see [6]) is fundamental to modern recursion theory; we make use of it in §2. Inductive definitions over the natural numbers have been studied extensively, beginning with Spector [11]. We list some of the results of that study in §1 for comparison with our new results on inductive definitions over the continuum. Note that for our purposes the continuum is identified with the Baire space ωω. It is possible to obtain simple inductive definitions over the continuum by introducing real parameters into inductive definitions over N—as in the definition of recursion in [5]. This is itself an interesting concept and is discussed further in [4]. These parametric inductive definitions, however, are in general weaker than the unrestricted set of inductive definitions, as is indicated below. In this paper we outline, for several classes of monotone inductive definitions over the continuum, solutions to the following characterization problems: (1) What is the class of sets which may be given by such inductive definitions ? (2) What is the class of ordinals which are the lengths of such inductive definitions ? These questions are made more precise below. Most of the results of this paper were announced in [2].

A classical result of descriptive set theory expresses every co-analytic subset of the real line as the union of an increasing sequence of Borel sets, the length of the chain being at most the first uncountable ordinal ℵ1 (see [5], [8]). An effective analog of this theorem, obtained by replacing co-analytic (Π11) and Borel (Δ11) with their lightface analogs, would represent every Π11 subset of the real line as the union of a chain of Δ11 sets. No such analog is true, however, because some Δ11 sets are not the union of their Δ11 subsets. For example, the set W, consisting of those reals which code well-orderings (in some standard coding) is Π11, but, by the boundedness principle ([3], [9]), any Δ11 subset of W contains codes only for well-orderings shorter than ω1, the first nonrecursive ordinal. Accordingly, we define the core of a Π11 set to be the union of its Δ11 subsets; clearly this is the largest subset of the given Π11 set for which an effective version of the classical representation could exist. In §1, we develop the elementary properties of cores of Π11 sets. For example, such a core is itself Π11 and can be represented as the union of a chain of Δ11 sets in a natural way; the chain will have length at most ω1. We show that the core of a Π11 set is “almost all” of the set, while on the other hand there are uncountable Π11 sets with empty cores.

An operator Γ mapping P(ω) to itself is inductive if Γ(A) ⊇ A for all A. For such an inductive operator Γ we define {Γα: α ∈ ORD} by letting Γ = ⌀, Γα + 1 = Γ(Γα) for all α, and Γβ = ⋃{Γα: α < β} for limit ordinals β. The closure ordinal ∣Γ∣ of Γ is the least ordinal α such that Γα+1 = Γα and the closure is Γ∣Γ∣. Let be a class of operators over the natural numbers. The closure ordinal ∣ ∣ of is the supremum of {∣Γ∣: Γ is an inductive operator and }. The closure algebra generated by is {A ⊆ ω: A is 1-1 reducible to for some inductive operator }. The inductive algebra generated by is {Γα: Γ is an inductive operator in and α < ∣Γ∣}. For A ∈ P(ω), is the supremum of the ordinals of well-orderings recursive in A. For , let be the supremum of . For example, it is well known that ω( ) = ω(∆10 = ω1, ω(Π11) = ω1 and ω(Δn1) = δn1 for n > 1 (the latter by definition).