Introduction

The notion of a recursively enumerable (r.e.) set, i.e. a set of integers whose members can be effectively listed, is a fundamental one. Another way of approaching this definition is via an approximating function { As}s∈w to the set A in the following sense: We begin by guessing x ∉ A>/i> at stage 0 (i.e. A0(x) ≥ 0); when x later enters A at a stage s + 1, we change our approximation from As(x) = 0 to As+1(x) = 1. Note that this approximation (for fixed) x may change at most once as s increases, namely when x enters A. An obvious variation on this definition is to allow more than one change: A set A is 2- r.e. (or d-r.e.) if for each x, As(x) change at most twice as s increases. This is equivalent to requiring the set A to be the difference of two r.e. sets A1 − A2. (Similarly, one can define n-r.e. sets by allowing at most n changes for each x.)

The notion of d-r.e. and n-r.e. sets goes back to Putnam [1965] and Gold [1965] and was investigated (and generalized) by Ershov [1968a, b, 1970]. Cooper showed that even in the Turing degrees, the notions of r.e. and dr. e. differ:

Theorem 1.1. (Cooper [1971[) There is a properly d-r.e. degree, i.e. a Turing degree containing a d-r.e. but no r.e. set.

In the eighties, various structural differences between the r.e. and the dr. e. degrees were exhibited by Arslanov [1985], Downey [1989], and others.

Abstract

Resource-bounded genericity concepts have been introduced by Ambos-Spies, Fleischhack and Huwig [AFH84], [AFH88], Lutz [Lu90], and Fenner [Fe91]. Though it was known that some of these concepts are incompatible, the relations among these notions were not fully understood. Here we survey these notions and clarify the relations among them by specifying the types of diagonalizations captured by the individual concepts. Moreover, we introduce two new, stronger resource-bounded genericity concepts corresponding to fundamental diagonalization concepts in complexity theory. First we define general genericity, which generalizes all of the previous concepts and captures both, standard finite extension arguments and slow diagonalizations. The second new concept, extended genericity, actually is a hierarchy of genericity concepts for a given complexity class which extends general genericity and in addition captures delayed diagonalizations. Moreover, this hierarchy will show that in general there is no strongest genericity concept for a complexity class. A similar hierarchy of genericity concepts was independently introduced by Fenner [Fe95].

Finally we study some properties of the Baire category notions on E induced by the genericity concepts and we point out some relations between resource-bounded genericity and resource-bounded random- ness.

Introduction

The finite extension method is a central diagonalization technique in computability theory (see e.g. [Ro67], [Od89], [Le83], [So87]). In a standard finite extension argument a set A of strings (or equivalently of numbers) is inductively defined by specifying longer and longer initial segments of it. The global property to be ensured for A by the construction is split into countably many subgoals, given as a list {Re: e≥ 0 } of so called requirements.

Abstract

A set A ⊆ ω is computably enumerable (c.e.), also called recursively enumerable, (r.e.), or simply enumerable, if there is a computable algorithm to list its members. Let ε denote the structure of the c.e. sets under inclusion. Starting with Post [1944] there has been much interest in relating the definable (especially ε-definable) properties of a c.e. set A to its “information content”, namely its Turing degree, deg(A), under ≤T, the usual Turing reducibility. [Turing 1939]. Recently, Harrington and Soare answered a question arising from Post's program by constructing a nonemptly ε-definable property Q(A) which guarantees that A is incomplete (A <TK). The property Q(A) is of the form (∃C)[A ⊂mC & Q−(A, C)], where A ⊂mC abbreviates that “A is a major subset of C”, and Q−(A,C) contains the main ingredient for incompleteness.

A dynamic property P(A), such as prompt simplicity, is one which is defined by considering how fast elements elements enter A relative to some simultaneous enumeration of all c.e. sets. If some set in deg(A) is promptly simple then A is prompt and otherwise tardy. We introduce here two new tardiness notions, small-tardy (A, C) and Q-tardy(A, C). We begin by proving that small-tardy(A, C) holds iff A is small in C (A ⊂sC) as defined by Lachlan [1968]. Our main result is that Q-tardy(A, C) holds iff Q−(A,C). Therefore, the dynamic property, Q-tardy(A, C), which is more intuitive and easier to work with than the ε-definable counterpart, Q−(A,C), is exactly equivalent and captures the same incompleteness phenomenon.

This is an informal list of some open problems in recursion theory, based on the list of open problems compiled during the Leeds Recursion Theory Year. Solutions have been announced for some of these problems. The current status of the questions below and of questions added after July 1995 can be found on the World Wide Web at html://www.math.uchicago.edu/͂ted.

Solutions and new problems are welcome and should be directed to T. A. Slaman at [email protected].

Abstract

It is shown that there is a non-trivial obstruction to block the extension of embeddings on the quotient structure of the recursively enumerable degrees modulo the cappable degrees. Therefore, Shoenfield's conjecture fails on that structure, which answers a question of Ambos- Spies, Jockusch, Shore, and Soare [1984], and Schwarz [1984] (also see Slaman [1994]).

Introduction

The recursively enumerable (r.e.) sets are these subsets of natural numbers (denoted ω) which can enumerated by an effective procedure (or a computable function from ω to ω). There is a notion of relatively computability (or Turing reducibility) among the r.e. sets (in fact, among all sets of natural numbers), which can view that one is more complicated or harder to compute than other. The equivalence classes under this notion of relatively computability of r.e. sets are called the r.e. (Turing) degrees. The set of all r.e. degrees (denoted R) is made into a partial ordering with least (0, the equivalence class of all recursive sets) and greatest (0′, the equivalence class which contains the halting problem) elements in the natural way, namely, the reducibility relation between r.e. sets induces a partial ordering on degrees. It is readily shown that finite supremum always exists in R. Therefore, R forms an upper semilattice.

ABSTRACT: We describe a general method to separate relativizations of structures arising from computability theory. The method is applied to the lattice of r.e. sets, and the partial orders of r.e. m–degrees and T–degrees. We also consider classes of oracles where all relativizations are elementarily equivalent. We hope that the paper can serve as well as an introduction to coding in these structures.

Introduction. The relativization of a concept from computability theory to an oracle set Z is obtained by expanding the underlying concept of computation in a way such that, at any step of the computation procedure, tests of the form “n ∈ Z”, where n is some number obtained previously in the computation, are allowed. For instance, the relativization of the concept of r.e. sets to Z is “set r.e. in Z”. In this paper, we study to what extent the isomorphism type and the theory of the relativization Az of a structure A from computability theory depend on the oracle set Z. We consider mainly the case that A is the structure ε of r.e. sets under inclusion or a degree structure on r.e. sets, but first discuss the case that A is the structure of DT all T –degrees or Dm of all m –degrees. In this case, is the structure of degrees of subsets of ω under many–one reductions via (total) functions recursive in Z, while is simply the upper cone of DT above the T –degree of Z.

In computability theory, Godel's incompleteness theorem [1934] finds expression in the definition of the jump operator. Thus, the Priedberg [1957] jump inversion theorem completely characterises the scope of the Godel undecidability phenomenon within the Kleene-Post [1954] degree structure for classifying unsolvable problems.

Minimal degrees of unsolvability naturally arise as the structural counterpart of decision problems whose solutions are extremely specialised (their solution does not have any other nontrivial applications). Spector [1956] showed that minimal degrees exist, while Sacks [1961] constructed one below 0′.

The first result concerning the jumps of minimal degrees was due to Yates [1970], who obtained a low minimal degree as a corollary to his construction of a minimal m below any given nonzero computably enumerable (or r.e.) degree. A global characterisation of such jumps was provided by the Cooper [1973] jump inversion theorem, while in the same paper it was shown that such a theorem could not hold locally (there are no high minimal degrees). The intuition that minimal degrees are in a sense close to 0 (the degree of the computable sets) was reinforced by Jockusch and Posner [1978], who found that all minimal degrees are in fact generalised low2 This, with Sasso's [1974] construction of a non-low minimal degree below ό, supported Jockusch's conjecture (see Yates [1974], p.235) that the jumps of minimal degrees below ό can be characterised as those ό-REA degrees which are low over 0′.

Introduction

The Medvedev lattice was introduced in [5] as an attempt to make precise the idea, due to Kolmogorov, of identifying true propositional formulas with identically “solvable” problems. A mass problem is any set of functions (throughout this paper “function” means total function from ω to ω; the small Latin letters f, g, h,… will be used as variables for functions). Mass problems correspond to informal problems in the following sense: given any “informal problem”, a mass problem corresponding to it is a set of functions which “solve” the problem, and at least one such function can be “obtained” by any “solution” to the problem (see [10]).

Example 1.1 If A, B ⊆ ω are sets, and φ is a partial function, then the following are mass problems:

1. {CA} (where CA is the characteristic function of A): this is called the problem of solvability of A; this mass problem will be denoted by the symbol SA;

2. {f : range(f) = A}: the problem of enumerability of A; this mass problem will be denoted by the symbol εA;

3. (Other examples) The problem of separability of A and B, i.e. {f : f−1(0) = A & f−1(1) = B}; of course, this mass problem is empty if A∩B ≠ Ø: it is absolutely impossible to “solve” the problem in this case. The problem of many-one reducibility of A to B: {f : f−l(B) = A}. The problem of extendibility of φ: {f : f ⊇ φ}.

Introduction

We consider genericity in the context of arithmetic. A set A ⊆ ε ω is called n-generic if it is Cohen-generic for n-quantifier arithmetic. By degree we mean Turing degree (of unsolvability). We call a degree n-generic if it has an n-generic representative. For a degree a, let D(≤ a) denote the set of degrees which are recursive in a. Since the set of n-generic sets is comeager, if some property is satisfied in D(≤ a) with a any generic degree, then in the sense of Baire category, we can say that it is satisfied in D(≤ a) for almost every degree a. So the structure of generic degrees plays an important role when we study the structure of D, the set of all degrees. For example, Slaman and Woodin [38] showed that there is a generic degree a such that if f is an automorphism of D and f(a) = a then f is identity. In this paper we mainly survey D(≤ a) when a is n-generic, as well as the properties of generic degrees in D. We assume the reader is familiar with the basic results of degree theory and arithmetical forcing. Feferman [4], Hinman [8], Hinman [9], and Lerman [25] are good references in this area. Odifreddi [29] is a good survey for basic notions and results for forcing and reducibilities. Jockusch [11] is a pioneering work in this area.

Section 1: Introduction

One of the most efficient methods for proving that a problem is undecidable is to code a second problem which is known to be undecidable into the given problem; a decision procedure for the original problem would then yield one for the second problem, so no such decision procedure can exist. Turing [1939] noticed that this method succeeds because of an inherent notion of information content, coded by a set of integers in the countable situation. This led him to introduce the relation of relative computability between sets as a way of expressing that the information content contained in one set was sufficient to identify the members of the second set.

Post [1944], and Kleene and Post [1954] tried to capture the notion of relative computability algebraically. They noticed that the pre-order relation induced on sets of integers by relative computability gave rise to an equivalence relation, and that the equivalence classes form a poset with least element. This structure, known as the degrees of unsolvability or just the degrees has since been intensively studied, and it is of interest whether the algebraic structure completely captures the notion of information content. This question reduces to the determination of whether the degrees are rigid, i.e., whether this algebraic structure has any non-trivial automorphisms, a question to which a positive result has recently been announced by Cooper.

One of the major problems one encounters in trying to produce, or rule out automorphisms of the degrees is that the structure is uncountable.

This volume is a collection of refereed research articles commemorating the Leeds Recursion Theory Year 1993-94. The year was funded principally by the (then) UK Science and Engineering Research Council, with additional support from the London Mathematical Society, European Twinning/Human Capital and Mobility Networks on ‘Complexity, Logic and Recursion Theory’, and on ‘Proof Theory and Computation’, a MURST-British Council travel grant, an EC PECO visiting fellowship, and with the backing of the Leeds University Department of Pure Mathematics. We thank them all for enabling an invigorating year.

It is fifteen years since the publication of the last Leeds Recursion Theory volume in this same series (LMS Lecture Notes 45). In that time the subject has made great strides. New methods have been developed and out of the immense technical machinery have finally emerged solutions to long-standing problems which originally motivated the pioneers some forty years ago, notably on definability, decidability and automorphisms for recursion theoretic structures. In addition the fundamental ideas concerning computation and recursion have naturally found their place at the interface between logic and theoretical computer science, and the feedback continues to motivate mathematical research in a variety of new directions. Thus the following contributions provide a picture of current ideas and methods in the ongoing investigations of the structure of the computable and non-computable universe. A number of the articles contain introductory and background material, which it is hoped will make the volume an invaluable source of information for specialist and non-specialist alike.

In previous chapters we have looked at the basic theory of knowledge and belief, along with some extensions and applications in the realms of computer science and artificial intelligence. The emphasis in this theory (or rather these theories and applications) was put upon the question of what is known or believed by the agent, and the logical systems that we have seen enable one to derive the knowledge or belief of such an agent.

In this chapter we shall switch the emphasis to the other side of the picture, namely whether one can say something about the ignorance of an agent as well. This is not as easy as it might seem at first glance. Of course, we can employ epistemic logic to express ignorance of the agent as well as its knowledge, e.g. by formulas of the form ¬Kϕ, expressing that ϕ is not known, and that the agent is thus ignorant about the truth of ϕ. One may even express a kind of total ignorance of the agent about the assertion ϕ by considering a formula of the form ¬Kϕ ∧ ¬K¬ϕ: the agent does not know ϕ nor does he know ¬ϕ. This is all perfectly fine, but how can one infer that the agent knows neither ϕ nor ¬ϕ in an actual situation? Of course, epistemic logic enables one to derive the agent's ignorance in some cases. For instance, since Kp → ¬K¬p is valid in S5, we can derive that, given Kp, the agent knows p, it holds that the agent must be ignorant about ¬p (i.e. ¬K¬p). However, now consider the following situation.