Abstract For a fixed set A. the number of queries to A needed in order to decide a set S is a measure of S's complexity. We consider the complexity of certain sets defined in terms of A: and, for m > 2, where #nA. (x1….. xn) = A(x1) + A(xn)(We identify with , where χA is the characteristic function of A.) If A is a nonrecursive semirecursive set or if A is a jump, we give tight bounds on the number of queries needed in order to decide ODDnA and MODmnA: • ODDnA can be decided with n parallel queries to A, but not with n − 1. • ODDnA can be decided with ⌈log(n + 1)⌉ sequential queries to A but not with ⌈log(n + 1)⌉ − 1. • MODmnA can be decided with ⌈n/m⌉ + ⌊n/m⌋ parallel queries to A but not with ⌈n/m⌉ + ⌊n/m⌋ − 1. • MODmnA can be decided with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ sequential queries to A but not with ⌈log(⌈n/m⌉ + ⌊n/m⌋ + 1)⌉ − 1. The lower bounds above hold for nonrecursive recursively enumerable sets A as well. (Interestingly, the lower bounds for recursively enumerable sets follow by a general result from the lower bounds for semirecursive sets.) In particular, every nonzero truth-table degree contains a set A such that ODDnA cannot be decided with n − 1 parallel queries to A. Since every truth-table degree also contains a set B such that ODDnB can be decided with one query to B, a set's query complexity depends more on its structure than on its degree. For a fixed set A, Q(n, A) = {S: S can be decided with n sequential queries to A}. Q∥ (n, A) = {S : S can be decided with n parallel queries to A}. We show that if A is semirecursive or recursively enumerable, but is not recursive, then these classes form non-collapsing hierarchies: • Q(0,A) ⊂ Q (1, A) ⊂ Q(2, A) ⊂ … Q∥ (0, A) ⊂ Q∥ (1, A) ⊂ Q∥ (2, A) ⊂ … The same is true if A is a jump.

We introduce two new notions of inductive inference: learning infinite recursive branches of recursive trees and learning winning strategies for closed recursive games. Branch learning can be seen as a natural generalization of learning functions, and learning winning strategies is a new approach to constructively find winning strategies for a special kind of Gale-Stewart games. These two independently motivated concepts turn out to be equivalent. In branch learning there appear new phenomena compared to function learning: e.g. we can show that learning and uniform computation are incomparable. In the setting of learning functions uniform computation is trivial. Another example is that there are two distinct natural definitions for BC-style branch learning which yield different classes. By studying different learning criteria, enumeration and computation of branches, and the effect of using an oracle for the halting problem we get a hierarchy built by the corresponding classes. All presented results also hold for winning strategy learning by the equivalence mentioned above. Additionally, we investigate the notion of counter strategy learning for closed recursive games.

One topic arising in recent research on “Bounded Query Classes” is to consider quantitative aspects of recursion theory, and in particular various notions of parameterized recursive approximations of sets. An important question is, for which values of the parameters – depending on the type of approximation – the approximated set is necessarily recursive. Beigel's Nonspeedup Theorem, Rummer's Cardinality Theorem and Trakhtenbrot's Theorem provide answers using nonuniform constructions. This paper investigates to which extend these constructions can be made uniform. Beigel's Nonspeedup Theorem is equivalent to the statement that every branch of a recursively enumerable tree of bounded width is recursive. There is no algorithm which computes a branch from the index of the tree, but there are nontrivial positive results by weakening the requirements as follows: For some fixed number k, an algorithm is wanted which, given an index of a tree, outputs a list of k programs such that at least one of them computes a branch of the tree up to finitely many errors. What is the least k for which this works? In this paper it is shown that, for recursively enumerable trees of width at most n, the least possible k is 2n−1. For trees arising from Trakhtenbrot's Theorem with parameters m, n, the optimal value is k = n − m + 1. In addition, several other, related classes of trees are investigated.

The way in which way Kolmogorov complexity and instance complexity affect properties of recursively enumerable (r.e.) sets is studied. The well-known $2\log n$ upper bound on the Kolmogorov complexity of initial segments of r.e. sets is shown to be optimal, and the Turing degrees of r.e. sets which attain this bound are characterized. The main part of the paper is concerned with instance complexity, introduced by Ko, Orponen, Schöning, and Watanabe in 1986, as a measure of the complexity of individual instances of a decision problem. They conjectured that for every r.e. nonrecursive set, the instance complexity is infinitely often at least as high as the Kolmogorov complexity. The conjecture is refuted by constructing an r.e. nonrecursive set with instance complexity logarithmic in the Kolmogorov complexity. This bound is optimal up to an additive constant. In the other extreme, the conjecture is established for many classes of complete sets, such as weak-truth-table-complete (wtt-complete) and Q-complete sets. However, there is a Turing-complete set for which it fails.

We study the fine structure of the classification of sets of natural numbers A according to the number of queries which are needed to compute the n-fold characteristic function of A. A complete characterization is obtained, relating the question to finite combinatorics. In order to obtain an explicit description we consider several interesting combinatorial problems.

Much structural work on NP-complete sets has exploited SAT′s d-self-reducibility. In this paper, we exploit the additional fact that SAT is a d-cylinder to show that NP-complete sets are p-superterse unless P = NP. In fact, every set that is NP-hard under polynomial-time no(1)-tt reductions is p-superterse unless P = NP. In particular, no p-selective set is NP-hard under polynomial-time no(1)-tt reductions unless P = NP. In addition, no easily countable set is NP-hard under Turing reductions unless P = NP. Self-reducibility does not seem to suffice far our main result: in a relativized world, we construct a d-self-reducible set in NP − P that is polynomial-time 2-tt reducible to a p-selective set.

In team learning one considers a set of n learning machines and requires that m out of n must be successful. Comparing the power of different teams of learning machines is a major topic of inductive inference. It is centered around the “inclusion problem”: When is an (m,n)-team more powerful than an (m′,n′)-team? In this paper we show that there are noninclusions of different strength for teams of finite learners (i.e., EX0-teams). We measure the strength of a noninclusion [m,n]EX0 ⊈[m′n′]EX0-team. If any such A exists then we may take A = K where K is the halting problem, and for Popperian learners a K-oracle is also necessary. In contrast, for the noninclusion [29,49]EX0&nsube[2,4]EX0 weaker oracles suffice, and we characterize them as exactly those sets which are Turing-equivalent to a complete and consistent extension of Peano Arithmetic.

Article Free Access Share on Inclusion problems in parallel learning and games (extended abstract) Authors: Martin Kummer Institut für Logik, Komplexität, und Deduktionssysteme, D-76128 Universität Karlsruhe, Germany Institut für Logik, Komplexität, und Deduktionssysteme, D-76128 Universität Karlsruhe, GermanyView Profile , Frank Stephan Institut für Logik, Komplexität, und Deduktionssysteme, D-76128 Universität Karlsruhe, Germany Institut für Logik, Komplexität, und Deduktionssysteme, D-76128 Universität Karlsruhe, GermanyView Profile Authors Info & Claims COLT '94: Proceedings of the seventh annual conference on Computational learning theoryJuly 1994Pages 287–298https://doi.org/10.1145/180139.181156Published:16 July 1994Publication History 3citation13DownloadsMetricsTotal Citations3Total Downloads13Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In analogy to the definition of the halting problem K, an r.e. set A is called a diagonal iff there is a computable numbering ψ of the class of all partial recursive functions such that A = {i ∈ ω: ψi(i)↓} (in that case we say that A is the diagonal of ψ). This notion has been introduced in [10]. It captures all r.e. sets that can be constructed by diagonalization. It was shown that any nonrecursive r.e. T-degree contains a diagonal, that for any diagonal A there is an r.e. nonrecursive nondiagonal B ≤TA, and that there are r.e. degrees a such that any r.e. set from a is a diagonal. In §2 of the present paper we show that the property “A is a diagonal” is elementary lattice theoretic (e.l.t.). This result complements and generalizes previous results of Harrington and Lachlan, respectively. Harrington (see [16, XV. 1]) proved that the property of being the diagonal of some Gödelnumbering (i.e., of being creative) is e.l.t., and Lachlan [12] proved that the property of being a simple diagonal (i.e., of being simple and not hh-simple [10]) is e.l.t. In §§3 and 4 we study the position of diagonals and nondiagonals inside the lattice of r.e. sets. We concentrate on an important class of nondiagonals, generalizing the maximal and hemimaximal sets: the -maximal sets. Using the results from [6] we are able to classify the -maximal sets that can be obtained as halfs of splittings of hh-simple sets.

Recently, H Herre developed a framework for nonmonotonic inference relations using closure operators I that associate with every theory Φ a subset I(Φ) of its ordinary models. He asked to what extent Herbrand's Theorem is valid for these model-based operators. In particular, he asked if it is true for ⊨min, ⊨re. and ⊨rec truth in all minimal, in all recursively enumerable, or in all recursive Herbrand models, respectively. We answer these questions negatively and discuss Herbrand's Theorem also for well-known nonmonotonic theories (the closed world assumption CWA, Reiter's default logic DL), Minker's weak generalized closed world assumption WGCWA and Clark's completion comp(P), as well as for monotonic theories, e.g. for ⊨d where d is a degree of unsolvability, and for theories where I is restricted to be a subset of the Herbrand models. In case of Clark's comp(P), Minker's WGCWA and ⊨d we get some interesting positive results. We also consider the compactness-property and its relation to Herbrand's Theorem in the more general setting of nonmonotonic relations ♭ that need not fit into Herre's framework.

Degrees of inferability have been introduced to measure the learning power of inductive inference machines which have access to an oracle. The classical concept of degrees of unsolvability measures the computing power of oracles. In this paper we determine the relationship between both notions. 1 Introduction We consider learning of classes of recursive functions within the framework of inductive inference [21]. A recent theme is the study of inductive inference machines with oracles ([8, 10, 11, 17, 24] and tangentially [12]; cf. [10] for a comprehensive introduction and a collection of all previous results.) The basic question is how the information content of the oracle (technically: its Turing degree) relates with its learning power (technically: its inference degree---depending on the underlying inference criterion). In this paper a definitive answer is obtained for the case of recursively enumerable oracles and the case when only finitely many queries to the oracle are allo...

Most theories of learning consider inferring a function f from either (1) observations about f or, (2) questions about f. We consider a scenario whereby the learner observes fand asks queries to some set A. EX[A] is the set of concept classes EX-learnable by an inductive inference machine with oracle A. A and F are EX-equivalent if EX[A] = EX[B]. The equivalence classes induced are the degrees of inferability. We prove several results about these degrees: (1) There are an uncountable number of degrees. (2) For A r.e., REC e BC[A] iff O'' ≤T A´, and there is evidence this holds for all sets A. (3) For A, B r.e., A ≡T B iff EX[A] = EX[B]. (4) There exists A, B low2 r.e., A|RB, EX[A] = EX[B]. (hence (3) is optimal).

In 1960 G. F. Rose [R] made the following definition: A function f: ω → ω is (m, n)-computable, where 1 ≤ m ≤ n, iff there exists a recursive function R: ωn → ωn such that, for all n-tuples (x1,…, xn) of distinct natural numbers, J. Myhill (see [McN, p. 393]) asked if f had to be recursive if m was close to n; B. A. Trakhtenbrot [T] responded by showing in 1963 that f is recursive whenever 2m > n. This result is optimal, because, for example, the characteristic function of any semirecursive set is (1,2)-computable. Trakhtenbrot's work was extended by E. B. Kinber [Ki1], using similar techniques. In 1986 R. Beigel [B] made a powerful conjecture, much more general than the above results. Partial verification, falling short of a full proof, appeared in [O]. Using new techniques, M. Kummer has recently established the conjecture, which will henceforth be referred to as the cardinality theorem (CT). It is the goal of this paper to show the connections between these various theorems, to review the methods used by Trakhtenbrot, and to use them to prove a special case of CT strong enough to imply Kinber's theorem (see §3). We thus have a hierarchy of results, with CT at the top. We will also include a discussion of Kummer's methods, but not a proof of CT.

In 1986, Beigel [Be87] (see also [Od89, III.5.9]) proved the nonspeedup theorem: if A, B ⊆ ω, and as a function of 2n variables can be computed by an algorithm which makes at most n queries to B, then A is recursive (informally, 2n parallel queries to a nonrecursive oracle A cannot be answered by making n sequential (or “adaptive”) queries to an arbitrary oracle B). Here, 2n cannot be replaced by 2n − 1. In subsequent papers of Beigel, Gasarch, Gill, Hay, and Owings the theory of “bounded query classes” has been further developed (see, for example, [BGGOta], [BGH89], and [Ow89]). The topic has also been studied in the context of structural complexity theory (see, for example, [AG88], [Be90], and [JY90]). If A ⊆ ω and n ≥ 1, let . Beigel [Be87] stated the powerful “cardinality conjecture” (CC): if A, B ⊆ ω, and can be computed by an algorithm which makes at most n queries to B, then A is recursive. Owings [Ow89] verified CC for n = 1, and, for n 1, he proved that A is recursive in the halting problem. We prove that CC is true for all n.

The most basic construction of an r.e. nonrecursive set—e.g. of the halting problem—proceeds by taking the diagonal of a recursive enumeration of all r.e. sets. We will answer the question of which r.e. sets can be constructed in this manner. If ψ is a computable numbering of some class of partial recursive functions, we define the diagonal of ψ to be the set Kψ ≔ {i ∈ ω ∣ ψi(i)↓}- It is well known that Kφ is creative if φ is a Gödelnumbering, and that for each creative set K there exists a Gödelnumbering φ such that K = Kφ. That is to say, the class of diagonals of Gödelnumberings is characterized as the class of creative sets. This class was shown to be elementary lattice theoretic (e.l.t.) by Harrington (see [So87, XV. 1.1]). We give a characterization of diagonals of arbitrary computable numberings of the class P1 of all partial recursive functions. To this end we introduce the notion of a semihyperhypersimple (shhs) set, which generalizes the notion of hyperhypersimplicity to nonsimple sets. It is shown that the diagonals of numberings of P1 are exactly the non-shhs sets. Then, properties of shhs sets are discussed. For example, for each nonrecursive r.e. set A there exists a nonrecursive shhs set B ≤TA, but not every r.e. T-degree contains a shhs set. These results build upon previous work by Downey and Stob [DSta]. The question whether the property “shhs” is (elementary) lattice theoretic remains open. A positive answer would give both an analog of Harrington's result mentioned above, and a generalization of the well-known fact, due to Lachlan [La68], that hyperhypersimplicity is e.l.t. Therefore, we suspect that shhs sets turn out to be useful in the study of the lattice of r.e. sets. Previously, for several constructions from recursion theory the role of the underlying numbering of P1 was investigated; see Martin ([Ma66a] or [So87, V.4.1]) and Lachlan ([La75] or [Od89, III.9.2]) for Post's simple set, and Jockusch and Soare ([JS73]; cf. also [So87, XII.3.6, 3.7]) for Post's hypersimple set. However, only Gödelnumberings were considered. An explanation for the greater variety which arises when arbitrary numberings of P1 are admitted is provided by the fact that the index set of Gödelnumberings is less complex than the index set of all numberings of P1. The former is Σ1-complete; the latter is Π4-complete.

We show that a translator ƒ: ω → ω from a Gödelnumbering φ into a direct sum η of a r.e. family of Friedbergnumberings satisfies ƒ ≰T0′. In particular, η cannot be a Gödelnumbering. In the following we use standard notation (cf.[3]): for i ≥ 1, Pi (respectively, Ri) is the set of partial (total) recursive i-place functions; φ is a Gödel numbering of P1. By φi, s we denote a recursive standard approximation for φi, i.e., φi, s is a finite function, φi, s ⊆ φi, s + 1, φi, s ⊆ φi, φi = ⋃ {φi, s ∣ s ≥ 0}, and a canonical index for φi, s can be computed uniformly in i, s (cf.[3, p. 16 f]). We call v ∈ P2 a numbering of P1 iff {λx.v(i, x)}i ∈ ω = P1; we denote λx.v(i, x) by vi. Let v and γ be numberings of P1. A total function g: ω → ω is called a translator from v into γ iff ∀i: vi = γg(i).