# Abstracts der Forschungsberichte Abstracts of the Research Reports

### 1

K. AMBOS-SPIES, D. DING:
Discontinuity of Cappings in the Recursively Enumerable Degrees and Strongly Nonbranching Degrees
October 1993, 33 pages

Abstract. We construct an r.e. degree a which possesses a greatest a-minimal pair b0, b1, i.e., r.e. degrees b0 and b1 such that b0,b1 > a, b0 meet b1 = a, and, for any other pair c0 and c1 with these properties, c0 less or equal bi and c1 less or equal b1-i for some i less or equal 1. By extending this result, we show that there are strongly nonbranching degrees which are not strongly noncappable. Finally, by introducing a new genericity concept for r.e. sets, we prove a jump theorem for the strongly nonbranching and strongly noncappable r.e. degrees.

### 2

A. NIES:
The Model Theory of the Structure of Recursively Enumerable Many-One Degrees
October 1993, 13 pages

Abstract. The theory of the r.e. m-degrees has the same computational complexity as true arithmetic. In fact, it is possible to define without parameters a standard model of arithmetic in this degree structure.

### 3

B. BORCHERT:
The Complexity of Mind Changes
October 1993, 9 pages
Download Postscript-File

Abstract. The notion of the maximal number of mind changes for a Boolean function was defined and applied in several contexts. An application in complexity theory is the result of Wagner and Wechsung that the classes of the Boolean closure of NP are exactly the classes of the Boolean hierarchy over NP. The aim of this paper is to study the complexity of determining the maximal number of mind changes of a Boolean function if the function is represented as a circuit.

### 4

A. NIES:
Undecidable Fragments of Elementary Theories
October 1993, 22 pages, 2 pages errata

Abstract. We introduce a general framework to prove undecidability of fragments. This is applied to fragments of theories arising in algebra and recursion theory. For instance, the forall-exist-forall-theory of the class of finite distributive lattices and of the p.o. of recursively enumerable many-one degrees are shown to be undecidable.

### 5

V. L. SELIVANOV:
Fine Hierarchies and Boolean Terms
November 1993, 28 pages

Abstract. We consider fine hierarchies in recursion theory, descriptive set theory, logic, and complexity theory. Main results state that sets of values of different Boolean terms coincide with levels of suitable fine hierarchies. This gives new short descriptions of these hierarchies and shows that collections of sets of values of Boolean terms are almost well-ordered by inclusion. For the sake of completeness we mention also some earlier results demonstrating usefulness of fine hierarchies.

### 6

B. BORCHERT:
On the Acceptance Power of Regular Languages
February 1994, 11 pages
Download Postscript-File

Abstract. Hertrampf, Lautemann, Schwentick, Vollmer and Wagner 1993 looked at complexity classes characterized by a regular acceptance language for the words of output bits produced by nondeterministic polynomial-time computations. Here the partial order from Zachos 1988 on relativizable complexity classes is considered which reflects the idea of oracle independent inclusion. The main result will be that this partial order on the complexity classes characterized by regular languages is atomic and therefore not dense. The atoms correspond to the classes NP, coNP and MODpP for p prime.

### 7

B. BORCHERT:
Predicate Classes and Promise Classes
April 1994, 18 pages
Download Postscript-File

Abstract. Considering computation trees produced by polynomial time nondeterministic computations one can define a complexity class by any predicate on computation trees, such classes will be called predicate classes. It will be shown that these classes are exactly the principal ideals of the polynomial time many-one reducibility. Additionally, the set of classes - which will be called promise classes - definable by promise functions instead of predicates will be shown to be equal to the set of countable ideals.

### 8

S. LEMPP, A. NIES:
The Undecidability of the Pi-4-theory for the r.e. wtt- and Turing-degrees
May 1994, 22 pages

Abstract. We show that the Pi-4-theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.

### 9

V. SELIVANOV:
Refining the Polynomial Hierarchy
July 1994, 20 pages

Abstract. By a result of J.Kadin the difference hierarchy over NP does not collapse if the polynomial hierarchy does not collapse. We extend this to a natural refinement of the polynomial hierarchy of length omega exp. omega. This refinement is generated from the levels of the polynomial hierarchy by the addition modulo 2 and is called here the plus-hierarchy. We consider also two refinements of the plus-hierarchy and discuss their possible applicability to the classification of some languages.

### 10

V. SELIVANOV:
On Recursively Enumerable Structures
July 1994, 20 pages

Abstract. We state some general facts on r.e. structures, e.g. we show that the free countable structures in quasivarieties are r.e. and construct acceptable numerations and universal r.e. structures in quasivarieties. The last facts are similar to the existence of acceptable numerations of r.e. sets and creative sets. We state a universality property of the acceptable numerations, classify some index sets and discuss their relation to other decision problems. These results show that the r.e. structures behave in some respects better than the recursive structures.

### 11

K. AMBOS-SPIES, H.-C. NEIS, S. A. TERWIJN:
Genericity and Measure for Exponential Time
August 1994, 19 pages

Abstract. Recently Lutz introduced a polynomial time bounded version of Lebesgue measure. He and others used this concept to investigate the quantitative structure of Exponential Time (E=DTIME(2 exp. lin)). Previously, Ambos-Spies, Fleischhack and Huwig introduced polynomial time bounded genericity concepts and used them for the investigation of structural properties of NP (under appropriate assumptions) and E. Here we relate these concepts to each other. We show that, for any c greate or equal 1, the class of (n exp. c)-generic sets has p-measure 1. This allows us to simplify and extend certain p-measure 1-results. To illustrate the power of generic sets we take the Small Span Theorem of Juedes and Lutz as an example and prove a generalization for bounded query reductions.

### 12

K. AMBOS-SPIES:
On Optimal Polynomial Time Approximations
September 1994, 15 pages

Abstract. Safe and unsafe polynomial time approximations were introduced by Meyer and Paterson [4] and Yesha [8], respectively. The question of which sets have optimal safe approximations was investigated by several authors (see e.g. [3,6,7]). Recently Duris and Rolim [2] considered the unsafe case and compared the existence of optimal polynomial time approximations for both cases. They left open the question, however, whether there are intractable sets with optimal unsafe approximations and whether there are sets with optimal unsafe approximations but without optimal safe approximations. Here we answer these questions affirmatively. Moreover, we consider a variant of Duris and Rolim's Delta-levelability concept related to the nonexistence of optimal unsafe approximations.

### 13

V.SELIVANOV:
Precomplete Numerations with Applications
October 1994, 59 pages

Abstract. We survey the current stage in the investigation of precomplete numerations and of some their subclasses. Recent results show that many naturally arising numerations are in a sense universal in a suitable class of precomplete numerations. This remarkable fact leads to deep manyfold connections and applications of precomplete numerations to other topics e.g. to hierarchies, index sets, degree structures and fixed point free degrees. We describe these applications in detail, so the paper is also a partial survey of the listed topics.

### 14

V. SELIVANOV:
Fine Hierarchy of Regular omega-Languages
October 1994, 13 pages

Abstract. By applying descriptive set theory we get several facts on the fine structure of regular omega-languages considered by K.Wagner. We present quite different, shorter proofs for main his results and get new results. Our description of the fine structure is new, very clear and automata-free. We prove also a closure property of the fine structure under Boolean operations. Our results demonstrate deep interconnections between descriptive set theory and theory of omega-languages.

### 15

K. AMBOS-SPIES, S. A. TERWIJN, X. ZHENG:
Resource Bounded Randomness and Weakly Complete Problems
January 1995, 14 pages

Abstract. We introduce and study resource bounded random sets based on Lutz«s concept of resource bounded measure. We concentrate on (n exp. c)-randomness (c greater or equal 1) which corresponds to the polynomial time bounded (p-) measure and which is adequate for studying the internal and quantitative structure of E=DTIME(2 exp. lin). However we will also comment on E2 = DTIME(2 exp. poly) and its corresponding (p2-) measure. First we show that the class of (n exp. c)-random sets has p-measure 1. This provides a new, simplified approach to p-measure 1-results. Next we compare randomness with genericity (in the sense of Ambos-Spies, Fleischhack and Huwig) and we show that (n exp. (c+1))-random sets are (n exp. c)-generic whereas the converse fails. From the former we conclude that (n exp. c)-random sets are not p-btt-complete for E. Our technical main results describe the distribution of the (n exp. c)-random sets under p-m-reducibility. We show that every (n exp. c)-random set in E has (n exp. k)-random predecessors in E for any k greater or equal 1 whereas the amount of randomness of the successors is bounded. We apply this result to answer a question raised by Lutz: We show that the class of weakly complete sets has measure 1 in E and that there are weakly complete problems which are not p-btt-complete for E.

### 16

K. AMBOS-SPIES:
Resource Bounded Genericity
August 1995, 55 pages

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 randomness.

### 17

B. BORCHERT, A. LOZANO:
Succinct Circuit Representations and Leaf Languages are Basically the same Concept
July 1995, 6 pages
Download Postscript-File

Abstract. This note connects two topics of Complexity Theory: The topic of succinct circuit representations initiated by Galperin and Wigderson [GW83], and the topic of leaf languages initiated by Bovet et al. [BCS92]. A graph with n nodes can - in the obvious way - be represented more succinctly by a circuit with 2logn input variables which assumes that the nodes are encoded and describes which nodes are connected by edges. This idea can be generalized from graphs to words, so that a circuit describes a word which is possibly exponentially longer. In this note the concept is slightly modified by shifting the length indicator from the circuit output to the problem input. This way, each language A determines its succinct version S(A) consisting of the coded pairs where c is a circuit and m is a binary number such that the length-m prefix of the word described by c is in A. In Bovet et al. [BCS92] it is shown how any language A (the leaf language) determines a complexity class C(A). It will be shown for any language A that its succinct version S(A) is polynomial-time many-one complete for C(A).

### 18

B. BORCHERT, D. RANJAN, F. STEPHAN:
On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions
December 1995, 19 pages
Download Postscript-File

Abstract. The paper analyzes in terms of polynomial time many-one reductions the computational complexity of several natural equivalence relations on Boolean functions which derive from replacing variables by expressions. Most of these computational problems turn out to be between co-NP and Sigma-p-2.

### 19

F. STEPHAN:
Noisy Inference and Oracles
January 1996, 30 pages
Download Postscript-File

Abstract. A learner noisily infers a function or set, if every correct item is presented infinitely often while in addition some incorrect data ("noise") is presented a finite number of times. It is shown that learning from a noisy informant is equal to finite learning with K-oracle from a usual informant. This result has several variants for learning from text and using different oracles. Furthermore, partial identification of all r.e. sets can cope also with noisy input.

### 20

F. STEPHAN:
Learning via Queries and Oracles
April 1996, 17 pages
Download Postscript-File

Abstract. Inductive inference considers two types of queries: Queries to a teacher about the function to be learned and queries to a non-recursive oracle. This paper combines these two types --- it considers three basic models of queries to a teacher (QEX[Succ], QEX[<] and QEX[+]) together with membership queries to some oracle. The results for each of these three models of query-inference are the same: If an oracle is omniscient for query-inference then it is already omniscient for EX. There is an oracle of trivial EX-degree, which allows nontrivial query-inference. Furthermore, queries to a teacher can not overcome differences between oracles and the query-inference degrees are a proper refinement of the EX-degrees. In the case of finite learning, the query-inference degrees coincide with the Turing degrees. Furthermore oracles can not close the gap between the different types of queries to a teacher.

### 22

K. AMBOS-SPIES, E. MAYORDOMO:
Resource-Bounded Measure and Randomness
August 1996, 52 pages
Download Postscript-File

Abstract. We survey recent results on resource-bounded measure and randomness in structural complexity theory. In particular, we discuss applications of these concepts to the exponential time complexity classes $\mbbe$ and $\mbbe_2$. Moreover, we treat time-bounded genericity and stochasticity concepts which are weaker than time-bounded randomness but which suffice for many of the applications in complexity theory.

### 23

B. BORCHERT, F. STEPHAN:
Looking for an Analogue of Rice's Theorem in Complexity Theory
November 1996, 14 pages
Download Postscript-File

Abstract. Rice's Theorem says that every nontrivial semantic property of programs is undecidable. It this spirit we show the following: Every nontrivial absolute (gap, relative) counting property of circuits is UP-hard with respect to polynomial-time Turing reductions.

### 24

W. MERKLE:
Exact Pairs for Abstract Bounded Reducibilities
November 1996, 20 pages
Download Postscript-File

Abstract. In an attempt to give a unified account of common properties of various resource bounded reducibilities, we introduce conditions on a binary relation \le_{r} between subsets of the natural numbers where \le_{r} is meant as a resource bounded reducibility. The conditions are a formalization of basic features shared by most resource bounded reducibilities which can be found in the literature. As our main technical result, we show that these conditions imply a result about exact pairs which has been previously shown by Ambos-Spies in a setting of polynomial time bounds: given some recursively presentable \le_{r}-ideal \cal{I} and some recursive \le_{r}-hard set B for \cal{I} which is not contained in \cal{I}, there is some recursive set C where B and C are an exact pair for \cal{I}, that is, \cal{I} is equal to the intersection of the lower \le_{r}-cones of B and C where C is not in \cal{I}. In particular, if the relation \le_{r} is in addition transitive and there are least sets, then every recursive set which is not in the least degree is half of a minimal pair of recursive sets.

### 25

F. STEPHAN:
On One-Sided Versus Two-Sided Classification
December 1996, 26 pages
Download Postscript-File

Abstract. One-sided classifiers are computable devices which read the characteristic function of a set and output a sequence of guesses which converges to 1 iff the set on the input belongs to the given class. Such a classifier is two-sided if the sequence of its output in addition converges to 0 on sets not belonging to the class. The present work obtains the below mentioned results for one-sided classes (= $\Sigma^0_2$ classes) w.r.t.\ four areas: Turing complexity, 1-reductions, index sets and measure. There are one-sided classes which are not two-sided. This can have two reasons: (1) the class has only high Turing complexity. Then there are some oracles which allow to construct noncomputable two-sided classifiers. (2) The class is difficult because of some topological constraints and then there are also no nonrecursive two-sided classifiers. For case (1), several results are obtained to localize the Turing complexity of certain types of one-sided sets. The concepts of 1-reduction, 1-completeness and simple sets is transferred to one-sided classes: There are 1-complete classes and simple classes, but no class is at the same time 1-complete and simple. The one-sided classes have a natural numbering. Most of the common index sets relative to this numbering have the high complexity $\Pi^1_1$: the index sets of the class $\{0,1\}^{\infty}$, the index set of the equality problem and the index set of all two-sided classes. On the other side the index set of the empty class has complexity $\Pi^0_2$; $\Pi^0_2$ and $\Sigma^0_2$ are the least complexities any non-trivial index set can have. Any one-sided class is measurable. It is shown that a one-sided class has effective measure 0 if it has measure 0, but that there are one-sided classes having measure 1 without having measure 1 effectively. The measure of a two-sided class can be computed in the limit.

### 26

S. KAUFMANN, F. STEPHAN:
Robust Learning with Infinite Additional Information
December 1996, 18 pages
Download Postscript-File

Abstract. The present work investigates Gold style algorithmic learning from input-output examples whereby the learner has access to oracles as additional information. Furthermore this access has to be robust, that means that a single learning algorithm has to succeed with every oracle which meets a given specification. The first main result considers oracles of the same Turing degree: Robust learning with any oracle from a given degree does not achieve more than learning without any additional information. The further work considers learning from function oracles which describe the whole class of functions to be learned in one of the following four ways: the oracle is a list of all functions in this class or a predictor for this class or a one-sided classifier accepting just the functions in this class or a martingale succeeding on this class. It is shown that for learning in the limit (Ex), lists are the most powerful additional information, the powers of predictors and classifiers are incomparable and martingales are of no help at all. Similar results are obtained for the criteria of predicting the next value, finite, Popperian and finite Popperian learning. Lists are omniscient for the criterion of predicting the next value but some classes can not be Ex-learned with any of these types of additional information. The class REC of all recursive functions is Ex-learnable with the help of a list, a predictor or a classifier.

### 27

W. MERKLE:
Structural Properties of Bounded Relations with an Application to NP Optimization Problems
December 1996, 16 pages
Download Postscript-File

Abstract. We introduce the notion bounded relation which comprises most resource bounded reducibilities to be found in the literature, including non-uniform reducibilities such as $\le ^{{\cal P}/poly}$. We state conditions on bounded relations which imply that every countable partial ordering can be embedded into every proper interval of the recursive sets, respectively functions. As corollaries, e obtain that every countable partial ordering can be embedded into every proper interval of $(REC,\le^{{\cal P}/poly}$, as well as into every proper interval between two maximization, respectively two minimization problems in the structures $(NPO,\le_E)$ and $(NPO,\le_L)$. We derive the results on the two latter structures by first representing maximization and minimization problems, respectively, by functions in $\omega^\omega$, then showing that the reducibilities induced on $\omega^\omeg$ by the relations $\le_L$ and $\le_E$ satisfy our assumptions. For these relations, we show further that the result about partial order embeddings extends to lattice embeddings of arbitrary countable distributive lattices where in addition the least or the greatest element of the lattice can be preserved. Among other corollaries, we obtain from the result on lattice embedding that every non-trivial $\cal NP$ optimization problem bounds a minimal pair.

### 28

K. AMBOS-SPIES, J. REIMANN:
Effective Baire Category Concepts
March 1997, 17 pages
Download Postscript-File

Abstract. Mehlhorn (1973) introduced an effective Baire category concept designed for measuring the size of classes of computable sets. This concept is based on effective extension functions. By considering partial extension functions, we introduce a stronger concept. Similar resource-bounded concepts have been previously introduced by Ambos-Spies et al. (1988) and Ambos-Spies (1996). By defining a new variant of the Banach-Mazur game, we give a game theoretical characterization of our category concept.

### 29

F. STEPHAN:
On the Structures Inside Truth-Table Degrees
October 1997, 42 pages
Download Postscript-File

Abstract. The following theorems on the structure inside nonrecursive truth-table degrees are established: D\"egtev's result that the number of bounded truth-table degrees inside a truth-table degree is at least two is improved by showing that this number is infinite. There are even infinite chains and antichains of bounded truth-table degrees inside the truth-table degrees which implies an affirmative answer to a question of Jockusch whether every truth-table degree contains an infinite antichain of many-one degrees. Some but not all truth-table degrees have a least bounded truth-table degree. The technique to construct such a degree is used to solve an open problem of Beigel, Gasarch and Owings: there are Turing degrees (constructed as hyperimmune-free truth-table degrees) which consist only of 2-subjective sets and do therefore not contain any objective set. Furthermore a truth-table degree consisting of three positive degrees is constructed where one positive degree consists of enumerable semirecursive sets, one of co-enumerable semirecursive sets and one of sets, which are neither enumerable nor co-enumerable nor semirecursive. So Jockusch's result that there are at least three positive degrees inside a truth-table degree is optimal. The number of positive degrees inside a truth-table degree can also be some other odd integers as for example nineteen, but it is never an even finite number.

### 30

K. AMBOS-SPIES, L. BENTZIEN:
Separating NP-Completeness Notions under Strong Hypotheses
November 1997, 29 pages
Download Postscript-File

Abstract. Lutz[16] proposed the study of the structure of the class NP=NTIME(poly) under the hypothesis that NP does not have p-measure 0 (with respect to Lutz's resource bounded measure [15]). Lutz and Mayordomo [18] showed that, under this hypothesis, NP-m-completeness and NP-T-completeness differ, and they conjectured that further NP-completeness notions can be separated. Here we prove this conjecture for the bounded-query reducibilities. In fact we consider a new weaker hypothesis, namely the assumption that NP is not p-meager with respect to the resource bounded Baire category concept of Ambos-Spies et al. [2]. We show that this category hypothesis is sufficient to get:
(i) For k>=2, NP-btt(k)-completeness is stronger than NP-btt(k+1)-completeness.
(ii) For k>=1, NP-bT(k)-completeness is stronger thanNP-bT(k+1)-completeness.
(iii) For every k^k-2, NP-bT(k-1)-completeness is not implied by NP-btt(k+1)-completeness and NP-btt(2^k-2)-completeness is not implied by NP-bT(k)-completeness.
(iv) NP-btt-completeness is stronger than NP-tt-completeness.

### 31

A.S. MOROZOV:
On Recovering Turing Degrees from Quotients of their Permutation Groups
February 1998, 25 pages
Download Postscript-File

Abstract. We study the interplay between Turing degrees $\bd$ and nontrivial factors of groups of all $\bd$--recursive permutations. We prove that the isomorphism type of any such factor group completely determines the degree $\bd$ and describe the definability of Turing degrees by elementary properties of these groups.
We reduce the study of elementary properties of these groups to the study of properties of degrees, being considered as classes of sets, in the first order language of arithmetics with added unary predicate.

### 32

W. GASARCH, F. STEPHAN:
A Techniques-Oriented Survey of Bounded Queries
March 1998, 40 pages
Download Postscript-File

Abstract. The present work gives an overview on the field of Bounded Queries including the subfields of frequency computation and verboseness. The main topic is finding quantitative notions for the complexity of non-recursive sets in terms of the local complexity of computing the n-fold characteristic function. This work presents in particular the various proof methods popular in this field.

### 33

W. MERKLE:
Lattice Embeddings for Abstract Bounded Reducibilities
April 1998, 92 pages
Download Postscript-File

Abstract. We give an abstract account of resource bounded reducibilities as exemplified by the polynomial time or logarithmically space bounded reudcibilities of Turing, truth-table, and many one type. We introduce a small set of axioms which are satisfied for most of the specific resource bounded reducibilities which appear in the literature. Some of the axioms are of a more algebraic nature, such as the requirement that the reducibility under consideration is a reflexive relation, while others are formulated in terms of recursion theory and for example are related to delayed computations of arbitrary recursive sets. We discuss basic consequences of these axioms and their relation to previous axiomatic approaches by Mehlhorn [31], Schmidt [41], Mueller [37], and, in a context of relativized Blum measure, by Lynch et al. [26]. As main technical result we show that for every reducibility which satisfies our axioms, every countable distributive lattice can be embedded into every proper interval of the structure induced on the recursive sets. This result extends a corresponding result for polynomial time bounded reducibilities due to Ambos-Spies [1], as well as work by Mehlhorn [31]. Mehlhorn shows from an apparently more restricitve set of assumptions that the recursive sets form a dense structure and claims that in fact every countable partial ordering can be embedded into every proper interval of the recusive sets.

### 34

F. STEPHAN, Y. VENTSOV:
Learning Algebraic Structures from Text
July 1998, 48 pages
Download Postscript-File

Abstract. The present work investigates the learnability of classes of substructures of some algebraic structure: submonoids and subgroups of some given group, ideals of some given commutative ring, subfields of a vector space. The learner sees all positive data but no negative one and converges to a program enumerating or computing the set to be learned. Besides semantical (BC) and syntactical (Ex) convergence also the more restrictive ordinal bounds on the number of mind changes are considered. The following is shown:
(a) Learnability depends much on the amount of semantic knowledge given at the synthesis of the learner where this knowledge is represented by programs for the algebraic operations, codes for prominent elements of the algebraic structure (like 0 and 1 in fields) and certain parameters (like the dimension of finite dimensional vector spaces). For several natural examples good knowledge of the semantics may enable to keep ordinal mind change bounds while restricted knowledge may either allow only BC-convergence or even not permit learnability at all.
(b) The class of all ideals of a recursive Noetherian ring is BC-learnable iff the ring is Noetherian. Furthermore, one has either only a BC-learner outputting enumerable indices or one can already get an Ex-learner converging to decision procedures and respecting an ordinal bound on the number of mind changes. The ring is Artinian iff the ideals can be Ex-learned with a constant bound on the number of mind changes, this constant is the length of the ring. Ex-learnability depends not only on the ring but also on the representation of the ring. Polynomial rings over the field of rationals with $n$ variables have exactly the ordinal mind change bound~$\omega^n$ in the standard representation. Similar results can be established for unars. Noetherian unars with one functioncan be learned with an ordinal mind change bound $a \omega$ for some~$a$.

### 35

A. NIES:
Coding Methods in Computability Theory and Complexity Theory
Habilitationsschrift, January 1998, 106 pages
Download Postscript-File

### 36

A. MOROZOV:
Groups of Sigma-permuations of Admissible Ordinals
July 1998, 20 pages
Download Postscript-File

Abstract. We consider the groups of Sigma-presentable permutations of recursively listed locally countable admissible sets. We prove that such groups are not Sigma-presentable over their admissible sets, prove all their automorphisms to be inner, and describe the normal structure of these groups.

### 37

A. MOROZOV:
On Sigma-definability of admissible sets
July 1998, 22 pages
Download Postscript-File

Abstract. We suggest a notion of Sigma-definability of an admissible set in another admissible set, prove the correctness of this notion, and give the group-theoretic criterion of Sigma-definability of one admissible set in another, for some class of admissible sets. Considering an admissible set as some computational capacity, we can say that the groups introduced in the paper as invariants are uniform measures of the computational power for admissible sets.
We also prove one result on definability over the constructive part of an admissible set.

### 38

K. AMBOS-SPIES:
A Note on Recursively Approximable Real Numbers
July 1998, 7 pages
Download Postscript-File

Abstract. In [1] Weihrauch and Zheng compare some notions of recursively approximable real numbers. Their two main results - stated in the terminology of [1] - are: There is a weakly computable real number which is not semi-computable, and there is a recursively enumerable real number which is not weakly computable. In [1] these theorems are directly proved by finite-injury arguments, where the proof of the first result uses the observation that the real corresponding to a d-r.e. set is weakly comutable. Here, by further exploring the relations between the computability properties of a real number and the location of the corresponding set in the difference hierarchy over the r.e. sets, we show that the two main results in [1] can be obtained from theorems on the r.e., d-r.e., and omega-r.e. degrees in the literature.

### 39

F. STEPHAN, S.A. TERWIJN:
The Complexity of Universal Text-Learners
October 1998, 18 pages
Download Postscript-File

Abstract. The present work deals with language learning from text. It considers universal learners for classes of languages in models of additional information and analyzes their complexity in terms of Turing-degrees. The following is shown: If the additional information is given by a set containing at least one index for each language from the class to be learned but no index for any language outside the class then there is a universal learner having the same Turing degree as the inclusion problem for recursively enumerable sets. This result is optimal in the sense that any further learner has the same or higher Turing degree. If the additional information is given by the index set of the class of languages to be learned then there is a computable universal learner. Furthermore, if the additional information is presented as an upper bound on the size of some grammar that generates the language then a high oracle is necessary and sufficient. Finally, it is shown that for the concepts of finite learning and learning from good examples, the index set of the class to be learned gives insufficient information: these criteria need due to the restrictive convergence-constraints the jump of the index set instead of the index set itself. So they have infinite access to the information of the index set in finite time.

### 40

J. CASE, S. JAIN, S. KAUFMANN, A. SHARMA, F. STEPHAN:
Predictive Learning Models for Concept Drift
November 1998, 26 pages
Download Postscript-File

Abstract. Concept drift means that the concept about which data is obtained may shift from time to time, each time after some minimum permanence. Except for this minimum permanence, the concept shifts may not have to satisfy any further requirements and may occur infinitely often. Within this work is studied to what extent it is still possible to predict or learn values for a data sequence produced by drifting concepts. Various ways to measure the quality of such predictions, including martingale betting strategies and density and frequency of correctness, are introduced and compared with one another. For each of these measures of prediction quality, for some interesting concrete classes, usefully established are (nearly) optimal bounds on permanence for attaining learnability. The concrete classes, from which the drifting concepts are selected, include regular languages accepted by finite automata of bounded size, polynomials of bounded degree, and exponentially growing sequences defined by recurrence relations of bounded size. Some important, restricted cases of drifts are also studied, for example, the case where the intervals of permanence are computable. In the case where the concepts shift only among finitely many possibilities from certain infinite, arguably practical classes, the learning algorithms can be considerably improved.

### 41

K. AMBOS-SPIES, L. BENTZIEN, P. A. FEJER, W. MERKLE, F. STEPHAN:
Collapsing Polynomial-Time Degrees
March 1999, 24 pages
Download Postscript-File

Abstract. For reducibilities r and s such that r is weaker than s, we say that the r-degree of A, i.e., the class of sets which are r-equivalent to A, collapses to the s-degree of A if both degrees coincide. We investigate for the polynomial-time bounded many-one, bounded truth-table, truth-table, and Turing reducibilities whether and under which conditions such collapses can occur. While we show that such collapses do not occur for sets which are hard for exponential time, we have been able to construct a recursive set such that its bounded truth-table degree collapses to its many-one degree. The question whether there is a set such that its Turing degree collapses to its many-one degree is still open; however, we show that such a set - if it exists - must be recursive.

### 42

W. MERKLE, Y. WANG:
Separation by Random Oracles and Almost Classes for Generalized Reducibilities
March 1999, 22 pages
Download Postscript-File

Abstract. Let C be the class of all sets (of natural numbers) and let $\le_r$ and $\le_s$ be two binary relations on C which are meant as reducibilities. Let both relations be closed under finite variation (of their set arguments) and consider the uniform distribution on C, which is obtained by choosing elements of C by independent tosses of a fair coin. Then we might ask for the probability that the lower $\le_r$-cone of a randomly chosen set X, that is, the class of all sets A with $A \le_r X$, differs from the lower $\le_s$-cone of X. By closure under finite variation, the Kolmogorov 0-1 law yields immediately that this probability is either 0 or 1; in case it is 1, the relations are said to be separable by random oracles. Again by closure under finite variation, for every given set A, the probability that a randomly chosen set X is in the upper cone of A w.r.t. $\le_r$ is either 0 or 1. Let $Almost_r$ be the class of sets for which the upper cone w.r.t. $\le_r$ has measure 1. In the following, results about separations by random oracles and about Almost classes are obtained in the context of generalized reducibilities, that is, for binary relations on C which can be defined by a countable set of total continuous functionals on C in the same way as the usual resource bounded reducibilities are defined by an enumeration of appropriate oracle Turing machines. The concept of generalized reducibility comprises all natural resource bounded reducibilities, but is more general; in particular, it does not involve any kind of specific machine model or even effectivity. The results on generalized reducibilities yields corollaries about specific resource bounded reducibilities, including several results which have been shown previously in the setting of time or space bounded Turing machine computations.

### 43

B. BORCHERT, R. SILVESTRI:
Dot Operators
April 1999, 18 pages
Download Postscript-File

Abstract. Well-known examples of dot operators are the existential, the counting, and the BP-operator. We will generalize this notion of a dot operator so that every language A will determine an operator A dot. In fact we will introduce the more general notion of promise dot operators for which the BP-operator is an example. Dot operators are a refinement of the leaf language concept because the class determined by a leaf language A equals A dot P. Moreover we are able to represent not only classes but reducibilities, in fact most of the known polynomial-time reducibilities can be represented by dot operators. We show that two languages determine the same dot operator if and only if they are reducible to each other by polylog-time computable monotone projections.

### 44

K. AMBOS-SPIES, B. BORCHERT, W. MERKLE, J. REIMANN, F. STEPHAN:
38. Workshop über Komplexitätstheorie, Datenstrukturen und effiziente Algorithmen
June 1999, 12 pages
Download Postscript-File

Abstract. The report contains the program and 10 research abstracts of talks given on that workshop.

### 45

K. HO, F. STEPHAN:
Simple sets and strong reducibilities
October 1999, 25 pages
Download Postscript-File

Abstract. We study connections between strong reducibilities and properties of computably enumerable sets such as simplicity. We call a class S of computably enumerable sets bounded iff there is an m-incomplete computably enumerable set A such that every set in S is m-reducible to A. For example, we show that the class of effectively simple sets is bounded; but the class of maximal sets is not. Furthermore, the class of computably enumerable sets Turing reducible to a computably enumerable set B is bounded iff B is low2. For r = bwtt, tt, wtt and T, there is a bounded class intersecting every computably enumerable r-degree; for r = c, d and p, no such class exists.

### 46

F. STEPHAN:
Degrees of Computing and Learning
Habilitationsschrift, November 1999, 163 pages
Download Postscript-File

Abstract. The present work focuses on oracles, in particular on computation and learning with the help of an oracle. Oracles allow the analysis of the difficulty of learning and computing problems. For example, the difficulty to check whether an enumerable set W given by its index e is infinite needs an oracle capable to compute the halting problem relative to the halting problem K. In learning theory, Adleman and Blum (AB91) showed that exactly the high oracles allow to Ex-learn the class REC of all total recursive functions. Also the difference between learning models has been analyzed in terms of the oracles necessary to make a problem S learnable with respect to some more pretentious Model 2 provided that the S is already learnable without the help of any oracle with respect to a less pretentious Model 1. The usefulness of the oracles with respect to a computation or learning task induces canonically a degree-structure on the oracles. Such degree-structures are research topics in their own right and there are numerous results on the degree-structures induced by computing (mostly on Turing, enumeration and many-one degrees). The present work (in particular in Chapter 2) gives an overview on the results about the degree-structures induced by learning.
For Turing reducibility, the question whether B is at least as powerful than A is equivalent to the question whether A can be computed relative to B, whence in this setting, degrees and their closures downward are always countable. In learning, an oracle B might be more powerful than A without giving any possibility to compute A relative to B, even in the limit. For example, Ex-learning has one uncountably infinite degree, namely the one of those oracles which allow to Ex-learn all classes of recursive functions. The structure of Ex-degrees is coarser than that of the Turing degrees. Only very restricted learning models like finite learning (Fin) generate the same degree-structure as the Turing reducibility.
Chapters 3 combines the notions of queries to oracles and of queries to teachers. Such a teacher answers questions --- posed in a specific query language --- on the function f to be learned. So the learner has more data on f as in the standard case. This extra-knowledge can sometimes be non-trivially combined with an oracle: There is an oracle A of trivial Ex-degree, which together with a teacher can learn a class S which can neither be learned from the oracle A alone nor from the teacher alone (Theorem 3.3.5).
An important research topic is the question to which extent errors and false information in the data-stream disturb learning. Many models of noisy data have the disadvantage that the disturbances do not only make learning difficult but do also permit identical data-streams for different concepts. Chapter 4 proposes a popular concept of noise which solves this problem: the basic idea is that each correct data-item occurs infinitely often while each incorrect one occurs only finitely often. Although each single item can be false, the data-stream as a whole determines which items are correct and which incorrect so that the function to be learned is uniquely determined by the data-stream. The central result is that Ex-learning functions from such data has a nice characterization in terms of learning with oracles: S is Ex-learnable from noisy data iff S is finitely learnable from noise-free data with the help of the oracle K.
The topic of Chapters 5 and 6 is the learning of sets and functions with infinite additional information. In both cases, the additional information is required to describe the whole class of languages to be learned and it must not be specific for a single set or function in S. Chapter 5 deals with various types of index-sets for classes of languages: if a set B contains for every language in S some index but no indices for languages outside S then a learner with a Turing degree which can solve the halting problem relative to the halting problem K can learn S with access to this oracle B. Such a learner is even class-independent since it works for every principally learnable S when the corresponding B is supplied. If B is an index-set in the classical sense, that is, if B contains exactly the indices e of the sets in S, then the learner can even be chosen to be recursive. In Chapter 5 it was required that the algorithm is universal in the sense that it worked for every S which is principally learnable, that is, learnable relative to some oracle. In contrast to this, the setting investigated in Chapter 6 permits that the algorithms are specific for the class S to be learned. However, the algorithms still have to be robust in the sense that they succeed with every oracle meeting the specification. Degree-theoretic descriptions of the oracle do not help much: if the learning-algorithm must be able to learn S with every oracle from a given m-degree then one can learn S even without an oracle. In contrast to this, syntactic descriptions of the class S turn out to be more helpful. The most powerful tools are lists of the functions in S. The considered syntactic descriptions are related to learning criteria, whence Chapter 6 is also some kind of study to which extent it is possible to translate learners of one type (represented by the oracle) uniformly into learners of an other type (represented by the learning algorithm using the oracle).
Classification is related to learning in the sense that, like a learner, a classifier reads the characteristic function of a given set A as a learner but converges only to 1 in the case that A is in the class S to be classified or converges to 0 in the case that A is not in the class S. This notion of two-sided classification can also be weakened to one-sided classification where the classifier on sets outside the class only outputs infinitely often a 0 without being required to converge to 0. Chapter 7 analyzes the relations between these two notions and the question, which oracles enable to transform a given one-sided classifier into a two-sided one.
While the preceding chapters focus on degree-structures more general than that of the Turing reducibility, Chapter 8 investigates the structures induced by stronger reducibility notions, mainly by those of truth-table reducibility and its even more restrictive variants. The central question is whether there are always infinitely many positive and bounded truth-table degrees inside a truth-table degree. Degtev (1973) showed that the number of bounded truth-table degrees inside a truth-table degree is at least 2. This result is improved by showing that this number in fact is always infinite. Moreover, there are infinite chains and antichains of bounded truth-table degrees inside every truth-table degree. The latter implies an affirmative answer to a question of Jockusch (1969) whether every truth-table degree contains an infinite antichain of many-one degrees. Some but not all truth-table degrees have a least bounded truth-table degree. The technique to construct such a degree is used to solve an open problem of Beigel, Gasarch and Owings (1989): There are Turing degrees (constructed as hyperimmune-free truth-table degrees) which consist only of 2-subjective sets and do therefore not contain any objective set. Furthermore, a truth-table degree consisting of three positive degrees is constructed where one positive degree consists of enumerable semirecursive sets, one of coenumerable semirecursive sets and one of sets, which are neither enumerable nor coenumerable nor semirecursive. So Jockusch's result that there are at least three positive degrees inside a truth-table degree is optimal. The number of positive degrees inside a truth-table degree can also be some other odd integers as for example nineteen, but it is never an even finite number.

### 47

K. AMBOS-SPIES, A. KUCERA:
Randomness in Computability Theory
February 2000, 15 pages
Download Postscript-File

Abstract. We discuss some aspects of algorithmic randomness and state some open problems in this area. The first part is devoted to the question "What is a computably random sequence?" Here we survey some of the approaches to algorithmic randomness and address some questions on these concepts. In the second part we look at the Turing degrees of Martin-Löf random sets. Finally, in the third part we deal with relativized randomness. Here we look at oracles which do not change randomness.

### 48

K. AMBOS-SPIES, W. MERKLE, J. REIMANN, S.A. TERWIJN:
Almost Complete Sets
June 2000, 18 pages
Download Postscript-File

Abstract. We show that there is a set which is almost complete but not complete under polynomial-time many-one (p-m) reductions for the class E of sets computable in deterministic time $2^{lin}$. Here a set A in a complexity class C is almost complete for C under some reducibility r if the class of the problems in C which do not r-reduce to A has measure 0 in C in the sense of Lutz's resource-bounded measure theory. We also show that the almost complete sets for E under polynomial-time bounded one-one length-increasing reductions and truth-table reductions of norm 1 coincide with the almost p-m-complete sets for E. Moreover, we obtain similar results for the class EXP of sets computable in deterministic time $2^{poly}$.

### 49

E. MARTIN, A. SHARMA, F. STEPHAN:
Learning Power and Language Expressiveness
July 2000, 19 pages
Download Postscript-File

Abstract. The topic of the present work is to study the relationship between the power of the learning algorithms on the one hand, and the expressive power of the logical language which is used to represent the problems to be learned on the other hand. The central question is whether enriching the language results in more learning power. In order to make the question relevant and nontrivial, it is required that both texts (sequences of data) and hypotheses (guesses) be translatable from the rich'' language into the poor'' one.
The issue is considered for several logical languages suitable to describe structures whose domain is the set of natural numbers. It is shown that enriching the language does not give any advantage for those languages which define a monadic second-order language being decidable in the following sense: there is a fixed interpretation in the structure of natural numbers such that the set of sentences of this extended language true in that structure is decidable. But enriching the original language even by only one constant gives an advantage if this language contains a binary function symbol (which will be interpreted as addition).
Furthermore, it is shown that behaviourally correct learning has exactly the same power as learning in the limit for those languages which define a monadic second-order language with the property given above, but has more power in case of languages containing a binary function symbol. Adding the natural requirement that the set of all structures to be learned is recursively enumerable, it is shown that it pays off to enrich the language of arithmetics for both finite learning and learning in the limit, but it does not pay off to enrich the language for behaviourally correct learning.

### 50

K. AMBOS-SPIES, J. REIMANN (Hg.):
Workshop Computability and Models, Heidelberg, 18.-20. Januar 2001
January 2001
Download Postscript-File

Abstract. The report contains program, abstracts, and the list of participants of the Workshop Computability and Models, which was held at Heidelberg, 18.-20. Januar 2001.

### 51

S. JAIN, F. STEPHAN:
Learning How to Separate
January 2001, 24 pages
Download Postscript-File

Abstract. The main question addressed in the present work is how to find effectively a recursive function separating two sets drawn arbitrarily from a given collection of disjoint sets. In particular, it is investigated in which cases it is possible to satisfy the following additional constraints: confidence where the learner converges on all data-sequences; conservativeness where the learner abandons only definitely wrong hypotheses; consistency where also every intermediate hypothesis is consistent with the data seen so far; set-driven learners whose hypotheses are independent of the order and the number of repetitions of the data-items supplied; learners where either the last or even all hypotheses are programs of total recursive functions.
The present work gives an overview of the relations between these notions and succeeds to answer many questions by finding ways to carry over the corresponding results from other scenarios within inductive inference. Nevertheless, the relations between conservativeness and set-driven inference needed a novel approach which enabled to show the following two major results:
(1) There is a class for which recursive separators can be found in a confident and set-driven way, but no conservative learner finds a (not necessarily total) separator for this class.
(2) There is a class for which recursive separators can be found in a confident and conservative way, but no set-driven learner finds a (not necessarily total) separator for this class.

### 52

W. MERKLE, F. STEPHAN:
Refuting Learning Revisited
April 2001, 29 pages
Download Postscript-File

Abstract. We consider, within the framework of inductive inference, the concept of refuting learning as introduced by Mukouchi and Arikawa, where the learner is not only required to learn all concepts in a given class but also has to explicitly refute concepts outside the class.
In the first part of the paper, we consider learning from text and introduce a concept of limit-refuting learning that is intermediate between refuting learning and reliable learning. We give characterizations for these concepts and show some results about their relative strength and their relation to confident learning.
In the second part of the paper we consider learning from texts that for some k contain all positive $\Pi_k$-formulae that are valid in the standard structure determined by the set to be learned. In this model, the following results are shown. For the language with successor, any countable axiomatizable class can be limit-refuting learned from $\Pi_1$-texts. For the language with successor and order, any countable axiomatizable class can be reliably learned from $\Pi_1$-texts and can be limit-refuting learned from $\Pi_2$-texts, whereas the axiomatizable class of all finite sets cannot be limit-refuting learned from $\Pi_1$-texts. For the full language of arithmetic, which contains in addition plus and times, for any even k there is an axiomatizable class that can be limit-refuting learned from $\Pi_{k+2}$-texts but not from $\Pi_{k}$-texts. A similar result with k+3 in place of k+2 holds with respect to the language of Presburger's arithmetic.

### 53

S. JAIN, F. STEPHAN:
A Tour of Robust Learning
October 2001, 27 pages
Download Postscript-File

Abstract. Barzdins conjectured that only recursively enumerable classes of functions can be learned robustly. This conjecture, which was finally refuted by Falk, initiated the study of notions of robust learning. The present work surveys research on robust learning and focusses on the recently introduced variants of uniformly robust and hyperrobust learning. Proofs are included for the (already konwn) results that uniformly robust Ex-learning is more restictive than robust Ex-learning, that uniformly robustly Ex-learnable classes are consistently learnable, that hyperrobustly Ex-learnable classes are in Num and that some hyperrobustly BC-learnable class is not in Num.

### 54

S. JAIN, F. STEPHAN, S.A. TERWIJN:
Counting Extensional Differences in BC-Learning
April 2002, 17 pages
Download Postscript-File

Abstract. Let BC be the model of behaviourally correct function learning as introduced by Barzdins and Case and Smith. We introduce a mind change hierarchy for BC, counting the number of extensional differences in the hypotheses of a learner. We compare the resulting models BC_n to models from the literature and discuss confidence, team learning, and finitely defective hypotheses. Among other things, we prove that there is a tradeoff between the number of semantic mind changes and the number of anomalies in the hypotheses. We also discuss consequences for language learning. In particular we show that, in contrast to the case of function learning, the family of classes that are confidently BC-learnable from text is not closed under finite unions.

### 55

V.S. HARIZANOV, F. STEPHAN:
On the Learnability of Vector Spaces
October 2002, 21 pages
Download Postscript-File

Abstract. The central topic of the paper is the learnability of the recursively enumerable subspaces of $V_{\infty }/V$, where $V_{\infty }$ is the standard recursive vector space over the rationals with countably infinite dimension, and $V$ is a given recursively enumerable subspace of $V_{\infty }$. It is shown that certain types of vector spaces can be characterized in terms of learnability properties: $V_{\infty }/V$ is behaviourally correct learnable from text iff $V$ is finite dimensional, $V_{\infty }/V$ is behaviourally correct learnable from switching the type of information iff $V$ is finite dimensional, $0$-thin, or $1$-thin. On the other hand, learnability from informant does not correspond to similar algebraic properties of a given space. There are $0$-thin spaces $W_{1}$ and $W_{2}$ such that $W_{1}$ is not explanatorily learnable from informant and the infinite product $(W_{1})^{\infty }$ is not behaviourally correct learnable, while $W_{2}$ and the infinite product $(W_{2})^{\infty }$ are both explanatorily learnable from informant.

### 56

S. JAIN, F. STEPHAN:
Learning by Switching Type of Information
October 2002, 19 pages
Download Postscript-File

Abstract. The present work is dedicated to the study of modes of data-presentation in the range between text and informant within the framework of inductive inference. In this study, the learner alternatingly requests sequences of positive and negative data. We define various formalizations of valid data presentations in such a scenario. We resolve the relationships between these different formalizations, and show that one of these is equivalent to learning from informant. We also show a hierarchy formed (for each of the formalizations studied) by considering the number of switches between requests for positive and negative data.

### 57

W. MERKLE, F. STEPHAN:
Trees and Learning
October 2002, 20 pages
Download Postscript-File

Abstract. We characterize FIN-, EX- and BC-learning, as well as the corresponding notions of team learning, in terms of isolated branches on effectively given sequences of trees. The more restrictive models of FIN-learning and strong-monotonic BC-learning are characterized in terms of isolated branches on a single tree. Furthermore, we discuss learning with additional information where the learner receives an index for a strongly recursive tree such that the function to be learned is isolated on this tree. We show that EX-learning with this type of additional information is strictly more powerful than EX-learning.

### 58

F. STEPHAN:
Martin-Löf Random and PA-complete sets
November 2002, 8 pages
Download Postscript-File

Abstract. A set A is Martin-Löf random iff the class {A} does not have Sigma^0_1-measure 0. A set A is PA-complete if one can compute relative to A a consistent and complete extension of Peano Arithmetic. It is shown that every Martin-Löf random set either permits to solve the halting problem K or is not PA-complete. This result implies a negative answer to the question of Ambos-Spies and Kucera whether there is a Martin-Loef random set not above K which is also PA-complete.

### 59

S. JAIN, W. MENZEL, F. STEPHAN:
Classes with Easily Learnable Subclasses
February 2003, 20 pages
Download Postscript-File

Abstract. It is well-known that infinite recursively enumerable sets have infinite recursive subsets. Similarly, one can study the relation between identifiable classes and subclasses which are identifiable under a more restrictive criterion. The chosen framework is inductive inference, in particular the criterion of explanatory learning (Ex) of recursive functions as introduced in Gold in 1967. Among the more restrictive criteria is finite learning, where the learner outputs on every function to be learned exactly one hypthesis which has to be correct. The topic of the present paper are the natural variants (a) and (b) below of the classical question whether a given learning criterion like finite learning is more restrictive than Ex-learning. (a) Does every infinite Ex-identifiable class have an infinite finitely identifiable subclass? (b) If an infiite Ex-identifiable class S has an infinite finitely identifiable subclass, does it necessarily follow that some appropriate learner Ex-identifies S as well as finitely identifies an infinte subclass of S? These questions are also treated in the context of ordinal mind change bounds.

### 60

R.G. DOWNEY, D.R. HIRSCHFELDT, A. NIES, F. STEPHAN:
Trivial Reals
February 2003, 26 pages
Download Postscript-File

Abstract. Solovay showed that there are noncomputable reals $\alpha$ such that $H( \alpha \upharpoonright n) \leq H(1^n)+O(1)$, where $H$ the prefix-free Kolmogorov complexity. Such $H$-trivialreals are interesting due to the connection between algorithmic complexity and effective randomness. We give a new, easier construction of an $H$-trivial real. We also analyze various computability-theoretic properties of the $H$-trivial reals, showing for example that no $H$-trivial real can compute the halting problem. Therefore, our construction of an $H$-trivial computably enumerable set is an easy, injury-free construction of an incomplete computably enumerable set. Finally, we relate the $H$-trivials to other classes of "highly nonrandom" reals that have been previously studied.

### 61

K. AMBOS-SPIES, E. BUSSE:
Automatic Forcing and Genericity: On the Diagonalization Strength of Finite Automata
Juni 2003, 24 pages
Download Postscript-File

Abstract. Algorithmic and resource-bounded Baire category and corresponding genericity concepts introduced in computability theory and computational complexity theory, respectively, have become elegant and powerful tools in these settings. Here we introduce some new genericity notions based on extension functions computable by finite automata which are tailored for capturing diagonalizations over regular sets and functions. We show that the generic sets obtained either by the partial regular extension functions of any given fixed constant length or by all total regular extension of constant length are just the sets with saturated (also called disjunctive) characteristic sequences. Here a sequence $\alpha$ is saturated if every string occurs in $\alpha$ as a substring. We also show that these automatic generic sets are not regular but may be context free. Furthermore, we introduce stronger automatic genericity notions based on regular extension functions of nonconstant length and we show that the corresponding generic sets are bi-immune for the classes of regular and context free languages.

### 62

R. BEIGEL, L. FORTNOW, F. STEPHAN:
Infinitely-Often Autoreducible Sets
Juni 2003, 16 pages
Download Postscript-File

Abstract. A set A is autoreducible if one can compute, for all x, the value A(x) by querying A only at places y different from x. Furthermore, A is infinitely-often autoreducible if, for infinitely many x, the value A(x) can be computed by querying A only at places y different from x; for all other x, the computation outputs a special symbol to signal that the reduction is undefined. It is shown that for polynomial time Turing and truth-table autoreducibility there are sets A, B, C in EXP such that A is not infinitely-often Turing autoreducible, B is Turing autoreducible but not infinitely-often truth-table autoreducible, C is truth-table autoreducible with g(n)+1 queries but not infinitely-often Turing autoreducible with g(n) queries. Here n is the length of the input, g is nondecreasing and there exists a polynomial p in n that bounds the computation time and values of g. Furthermore, connections between notions of infinitely-often autoreducibility and notions of approximability are investigated. The Hausdorff-dimension of the class of sets which are not infinitely-often autoreducible is shown to be 1.

### 63

A. NIES, J. REIMANN:
A lower cone in the wtt degrees of non-integral effective dimension
Juni 2003, 16 pages
Download PDF-File

Abstract. For any rational number r, we show that there exists a set A (weak truth-table reducible to the halting problem) such that any set B weak truth-table reducible to it has effective Hausdorff dimension at most r, where A itself has dimension at least r. This implies, for any rational r, the existence of a wtt-lower cone of effective dimension r.

### 64

D. R. HIRSCHFELDT, A. NIES, F. STEPHAN:
Using random sets as oracles
October 2006, 18 pages
Download PS-File

Abstract. Let R be a notion of algorithmic randomness for individual subsets of the natural numbers. We say B is a base for R-randomness if there is a Z such that Z is R-random relative to B and B is Turing reducible to Z.We show that the bases for 1-randomness are exactly the K-trivial sets and discuss several consequences of this result. We also show that the bases for computable randomness include every set Turing reducible to the halting problem that is not diagonally noncomputable, but no set of PA-degree. As a consequence, we conclude that any difference of finitely computably enumerable set is a base for computable randomness iff it is Turing incomplete.

Verantwortlich: E-Mail
Letzte Änderung: 04.01.2013