We study the Medvedev degrees of mass problems with distinguished topological properties, such as denseness, closedness, or discreteness. We investigate the sublattices generated by these degrees; the prime ideal generated by the dense degrees and its complement, a prime filter; the filter generated by the nonzero closed degrees and the filter generated by the nonzero discrete degrees. We give a complete picture of the relationships of inclusion holding between these sublattices, these filters, and this ideal. We show that the sublattice (...) of the closed Medvedev degrees is not a Brouwer algebra. We investigate the dense degrees of mass problems that are closed under Turing equivalence, and we prove that the dense degrees form an automorphism base for the Medvedev lattice. The results hold for both the Medvedev lattice on the Baire space and the Medvedev lattice on the Cantor space. (shrink)

We show that every finite lattice is embeddable into the Σ 0 2 enumeration degrees via a lattice-theoretic embedding which preserves 0 and 1.

Sacks [2] has asked whether there exists a uniform solution to Post's problem, i.e. an enumeration operation W such that $\mathbf{d} for every degree d. It is shown here that if such an operation W exists it cannot itself in a particular technical sense be uniform. In fact, the jump operation is characterized amongst such uniform enumeration operations by the condition: $\mathbf{d} for all d. In addition, it is proved that the only other uniform enumeration operations such that d ≤ (...) W (d) for all d are those which equal the identity operation above some fixed degrees. (shrink)

In [2], Jockusch and Shore have introduced a new hierarchy of sets and operators called the REA hierarchy. In this note we prove analogues of the Friedberg Jump Theorem and the Sacks Jump Theorem for many REA operators. MSC: 03D25, 03D55.

For automatic and recursive graphs, we investigate the following problems: (A) existence of a Hamiltonian path and existence of an infinite path in a tree (B) existence of an Euler path, bounding the number of ends, and bounding the number of infinite branches in a tree (C) existence of an infinite clique and an infinite version of set cover The complexity of these problems is determined for automatic graphs and, supplementing results from the literature, for recursive graphs. Our results show (...) that these problems (A) are equally complex for automatic and for recursive graphs ( $\Sigma _{1}^{1}\text{-complete}$ ), (B) are moderately less complex for automatic than for recursive graphs (complete for different levels of the arithmetic hierarchy), (C) are much simpler for automatic than for recursive graphs (decidable and $\Sigma _{1}^{1}\text{-complete}$ , resp.). (shrink)

Osvald Demuth studied constructive analysis from the viewpoint of the Russian school of constructive mathematics. In the course of his work he introduced various notions of effective null set which, when phrased in classical language, yield a number of major algorithmic randomness notions. In addition, he proved several results connecting constructive analysis and randomness that were rediscovered only much later.In this paper, we trace the path that took Demuth from his constructivist roots to his deep and innovative work on the (...) interactions between constructive analysis, algorithmic randomness, and computability theory. We will focus specifically on Demuth’s work on the differentiability of Markov computable functions and his study of constructive versions of the Denjoy alternative, Demuth’s independent discovery of the main notions of algorithmic randomness, as well as the development of Demuth randomness, and the interactions of truth-table reducibility, algorithmic randomness, and semigenericity in Demuth’s work. (shrink)

Is there a nontrivial automorphism of the Turing degrees? It is a major open problem of computability theory. Past results have limited how nontrivial automorphisms could possibly be. Here we consider instead how an automorphism might be induced by a function on reals, or even by a function on integers. We show that a permutation of ω cannot induce any nontrivial automorphism of the Turing degrees of members of 2ω, and in fact any permutation that induces the trivial automorphism must (...) be computable.A main idea of the proof is to consider the members of 2ω to be probabilities, and use statistics: from random outcomes from a distribution we can compute that distribution, but not much more. (shrink)

In this paper I discuss the topics of mechanism and algorithmicity. I emphasise that a characterisation of algorithmicity such as the Turing machine is iterative; and I argue that if the human mind can solve problems that no Turing machine can, the mind must depend on some non-iterative principle — in fact, Cantor's second principle of generation, a principle of the actual infinite rather than the potential infinite of Turing machines. But as there has been theorisation that all physical systems (...) can be represented by Turing machines, I investigate claims that seem to contradict this: specifically, claims that there are noncomputable phenomena. One conclusion I reach is that if it is believed that the human mind is more than a Turing machine, a belief in a kind of Cartesian dualist gulf between the mental and the physical is concomitant. (shrink)

The aim of this paper is to shed light on our understanding of large scale properties of infinite strings. We say that one string $\alpha $ has weaker large scale geometry than that of $\beta $ if there is color preserving bi-Lipschitz map from $\alpha $ into $\beta $ with small distortion. This definition allows us to define a partially ordered set of large scale geometries on the classes of all infinite strings. This partial order compares large scale geometries of (...) infinite strings. As such, it presents an algebraic tool for classification of global patterns. We study properties of this partial order. We prove, for instance, that this partial order has a greatest element and also possess infinite chains and antichains. We also investigate the sets of large scale geometries of strings accepted by finite state machines such as Büchi automata. We provide an algorithm that describes large scale geometries of strings accepted by Büchi automata. This connects the work with the complexity theory. We also prove that the quasi-isometry problem is a $\Sigma _2^0$ -complete set, thus providing a bridge with computability theory. Finally, we build algebraic structures that are invariants of large scale geometries. We invoke asymptotic cones, a key concept in geometric group theory, defined via model-theoretic notion of ultra-product. Partly, we study asymptotic cones of algorithmically random strings, thus connecting the topic with algorithmic randomness. (shrink)

One construal of convergent realism is that for each clear question, scientific inquiry eventually answers it. In this paper we adapt the techniques of formal learning theory to determine in a precise manner the circumstances under which this ideal is achievable. In particular, we define two criteria of convergence to the truth on the basis of evidence. The first, which we call EA convergence, demands that the theorist converge to the complete truth "all at once". The second, which we call (...) AE convergence, demands only that for every sentence in the theorist's language, there is a time at which the theorist settles the status of the sentence. The relative difficulties of these criteria are compared for effective and ineffective agents. We then examine in detail how the enrichment of an agent's hypothesis language makes the task of converging to the truth more difficult. In particular, we parametrize first-order languages by predicate and function symbol arity, presence or absence of identity, and quantifier prefix complexity. For nearly each choice of values of these parameters, we determine the senses in which effective and ineffective agents can converge to the complete truth on an arbitrary structure for the language. Finally, we sketch directions in which our learning theoretic setting can be generalized or made more realistic. (shrink)

§0. Introduction. In [16], Barwise described his graduate study at Stanford. He told of his interactions with Kreisel and Scott, and said how he chose Feferman as his advisor. He began working on admissible fragments of infinitary logic after reading and giving seminar talks on two Ph.D. theses which had recently been completed: that of Lopez-Escobar, at Berkeley, on infinitary logic [46], and that of Platek [58], at Stanford, on admissible sets.Barwise's work on infinitary logic and admissible sets is described (...) in his thesis [4], the book [13], and papers [5]—[16]. We do not try to give a systematic review of these papers. Instead, our goal is to give a coherent introduction to infinitary logic and admissible sets. We describe results of Barwise, of course, because he did so much. In addition, we mention some more recent work, to indicate the current importance of Barwise's ideas. Many of the central results are stated without proof, but occasionally we sketch a proof, to indicate how the ideas fit together.Chapters 1 and 2 describe infinitary logic and admissible sets at the time Barwise began his work, circa 1965. From Chapter 3 on, we survey the developments that took place after Barwise appeared on the scene.§1. Background on infinitary logic. In this chapter, we describe the situation in infinitary logic at the time that Barwise began his work. We need some terminology. By a vocabulary, we mean a set L of constant symbols, and relation and operation symbols with finitely many argument places. As usual, by an L-structureM, we mean a universe set M with an interpretation for each symbol of L. (shrink)

Let Γ be a collection of relations on the reals and let M be a set of reals. We call M a perfect set basis for Γ if every set in Γ with parameters from M which is not totally included in M contains a perfect subset with code in M. A simple elementary proof is given of the following result (assuming mild regularity conditions on Γ and M): If M is a perfect set basis for Γ, the field of (...) every wellordering in Γ is contained in M. An immediate corollary is Mansfield's Theorem that the existence of a Σ 1 2 wellordering of the reals implies that every real is constructible. Other applications and extensions of the main result are also given. (shrink)

A standard result about hyperdegrees is proved (under PD) for all ▵ 1 2n + 1 -degrees.

A standard result about hyperdegrees is proved for allΔ2n+11-degrees.

We study topological constructions in the recursion theoretic framework of the lattice of recursively enumerable open subsets of a topological space X. Various constructions produce complemented recursively enumerable open sets with additional recursion theoretic properties, as well as noncomplemented open sets. In contrast to techniques in classical topology, we construct a disjoint recursively enumerable collection of basic open sets which cannot be extended to a recursively enumerable disjoint collection of basic open sets whose union is dense in X.

In [5], Metakides and Nerode introduced the study of recursively enumerable substructures of a recursively presented structure. The main line of study presented in [5] is to examine the effective content of certain algebraic structures. In [6], Metakides and Nerode studied the lattice of r.e. subspaces of a recursively presented vector space. This lattice was later studied by Kalantari, Remmel, Retzlaff and Shore. Similar studies have been done by Metakides and Nerode [7] for algebraically closed fields, by Remmel [10] for (...) Boolean algebras and by Metakides and Remmel [8] and [9] for orderings. Kalantari and Retzlaff [4] introduced and studied the lattice of r.e. subsets of a recursively presented topological space. Kalantari and Retzlaff consideredX, a topological space with ⊿, a countable basis. This basis is coded into integers and with the help of this coding, r.e. subsets ofωgive rise to r.e. subsets ofX. The notion of “recursiveness” of a topological space is the natural next step which gives rise to the question of what should be the “degree” of an r.e. open subset ofX? It turns out that any r.e. open set partitions ⊿; into four sets whose Turing degrees become central in answering the question raised above.In this paper we show that the degrees of the elements of the partition of ⊿ imposed by an r.e. open set can be “controlled independently” in a sense to be made precise in the body of the paper. In [4], Kalantari and Retzlaff showed that givenAany r.e. set andany r.e. open subset ofX, there exists an r.e. open set ℋ which is a subset ofand is dense in and in whichAis coded. This shows that modulo a nowhere dense set, an r.e. open set can become as complicated as desired. After giving the general technical and notational machinery in §1, and giving the particulars of our needs in §2, in §3 we prove that the set ℋ described above could be made to be precisely of degree ofA. We then go on and establish various results on the mentioned partitioning of ⊿. One of the surprising results is that there are r.e. open sets such that every element of partitioning of ⊿ is of a different degree. Since the exact wording of the results uses the technical definitions of these partitioning elements, we do not summarize the results here and ask the reader to examine §3 after browsing through §§1 and 2. (shrink)

Given a graph G, we say that a subset D of the vertex set V is a dominating set if it is near all the vertices, in that every vertex outside of D is adjacent to a vertex in D. A domatic k-partition of G is a partition of V into k dominating sets. In this paper, we will consider issues of computability related to domatic partitions of computable graphs. Our investigation will center on answering two types of questions for (...) the case when k = 3. First, if domatic 3-partitions exist in a computable graph, how complicated can they be? Second, a decision problem: given a graph, how difficult is it to decide whether it has a domatic 3-partition? We will completely classify this decision problem for highly computable graphs, locally finite computable graphs, and computable graphs in general. Specifically, we show the decision problems for these kinds of graphs to be ${\Pi^{0}_{1}}$ -, ${\Pi^{0}_{2}}$ -, and ${\Sigma^{1}_{1}}$ -complete, respectively. (shrink)

We show that the Turing degrees are not sufficient to measure the complexity of continuous functions on [0, 1]. Computability of continuous real functions is a standard notion from computable analysis. However, no satisfactory theory of degrees of continuous functions exists. We introduce the continuous degrees and prove that they are a proper extension of the Turing degrees and a proper substructure of the enumeration degrees. Call continuous degrees which are not Turing degrees non-total. Several fundamental results are proved: a (...) continuous function with non-total degree has no least degree representation, settling a question asked by Pour-El and Lempp; every non-computable f $\epsilon \mathcal{C}[0, 1]$ computes a non-computable subset of $\mathbb{N}$ ; there is a non-total degree between Turing degrees $a _\eqslantless_{\tau}$ b iff b is a PA degree relative to a; $\mathcal{S} \subseteq 2^{\mathbb{N}}$ is a Scott set iff it is the collection of f-computable subsets of $\mathbb{N}$ for some f $\epsilon \mathcal{C}[O, 1]$ of non-total degree; and there are computably incomparable f, g $\epsilon \mathcal{C}[0, 1]$ which compute exactly the same subsets of $\mathbb{N}$ . Proofs draw from classical analysis and constructive analysis as well as from computability theory. (shrink)

In this paper a new property of theories, called effective retractability is introduced and used to obtain a characterization for the degrees of subtheories of arithmetic and set theory. By theory we understand theory in standard formalization as defined by Tarski [10]. The word degree refers to the Kleene-Post notion of degree of recursive unsolvability [2]. By the degree of a theory we mean, of course, the degree associated with its decision problem via Gödel numbering.