Computability - Volume 8, issue 3-4

Authors: Brattka, Vasco | Downey, Rod | Knight, Julia F. | Lempp, Steffen

Article Type: Editorial

DOI: 10.3233/COM-180103

Citation: Computability, vol. 8, no. 3-4, pp. 191-191, 2019

Authors: Andrews, Uri | Sorbi, Andea

Article Type: Research Article

Abstract: We study computably enumerable equivalence relations (abbreviated as ceers ) under computable reducibility, and we investigate the resulting degree structure Ceers , which is a poset with a smallest and a greatest element. We point out a partition of the ceers into three classes: the finite ceers, the light ceers, and the dark ceers. These classes yield a partition of the degree structure as well, and in the language of posets the corresponding classes of degrees are first order definable within Ceers . There is no least, no maximal, no greatest dark degree, but there are …infinitely many minimal dark degrees. We study joins and meets in Ceers , addressing the cases when two incomparable degrees of ceers X , Y have or do not have a join or a meet according to where X , Y are located in the classes of the aforementioned partition: in particular no pair of dark ceers has a join, and no pair in which at least one ceer is dark has a meet. We also exhibit examples of ceers X , Y having as a join their uniform join X ⊕ Y , but also examples with a join which is strictly less than X ⊕ Y . We study join-irreducibility and meet-irreducibility: every dark ceer is both join-, and meet-irreducible. In particular we characterize the property of being meet-irreducible for a ceer E , by showing that it coincides with the property of E being self-full, meaning that every reducibility from E to itself is in fact surjective on its equivalence classes (this property properly extends darkness). We then study the quotient structure obtained by dividing the poset Ceers by the degrees of the finite ceers, and study joins and meets in this quotient structure: interestingly, contrary to what happens in the structure of ceers, here there are pairs of incomparable equivalence classes of dark ceers having a join, and every element different from the greatest one is meet-reducible. In fact in this quotient structure, every degree different from the greatest one has infinitely many strong minimal covers, whereas in Ceers every degree different from the greatest one has either infinitely many strong minimal covers, or the cone strictly above it has a least element: this latter property characterizes the self-full degrees. We look at automorphisms of Ceers , and show that there are continuum many automorphisms fixing the dark ceers, and continuum many automorphisms fixing the light ceers. Finally, we compute the complexity of the index sets of the classes of ceers studied in the paper. Show more

Keywords: Computably enumerable equivalence relation, computable reducibility on equivalence relations, dark ceers, light ceers, self-fullness

DOI: 10.3233/COM-180098

Citation: Computability, vol. 8, no. 3-4, pp. 193-241, 2019

Authors: Chih, Ellen | Downey, Rod G.

Article Type: Research Article

Abstract: We prove that if A is a non-low c.e. set, then there exists noncomputable sets A 1 ⊔ A 2 = A splitting A with A 1 non-low.

Keywords: Splitting, low, computably enumerable set, non-uniformity, domination

DOI: 10.3233/COM-180093

Citation: Computability, vol. 8, no. 3-4, pp. 243-252, 2019

Authors: Csima, Barbara F. | Dzhafarov, Damir D. | Hirschfeldt, Denis R. | Jockusch, Jr., Carl G. | Solomon, Reed | Brown Westrick, Linda

Article Type: Research Article

Abstract: Hindman’s Theorem (HT) states that for every coloring of N with finitely many colors, there is an infinite set H ⊆ N such that all nonempty sums of distinct elements of H have the same color. The investigation of restricted versions of HT from the computability-theoretic and reverse-mathematical perspectives has been a productive line of research recently. In particular, HT k ⩽ n is the restriction of HT to sums of at most n many elements, with at most k colors allowed, and HT …k = n is the restriction of HT to sums of exactly n many elements and k colors. Even HT 2 ⩽ 2 appears to be a strong principle, and may even imply HT itself over RCA0 . In contrast, HT 2 = 2 is known to be strictly weaker than HT over RCA0 , since HT 2 = 2 follows immediately from Ramsey’s Theorem for 2-colorings of pairs. In fact, it was open for several years whether HT 2 = 2 is computably true. We show that HT 2 = 2 and similar results with addition replaced by subtraction and other operations are not provable in RCA0 , or even WKL0 . In fact, we show that there is a computable instance of HT 2 = 2 such that all solutions can compute a function that is diagonally noncomputable relative to ∅ ′ . It follows that there is a computable instance of HT 2 = 2 with no Σ 2 0 solution, which is the best possible result with respect to the arithmetical hierarchy. Furthermore, a careful analysis of the proof of the result above about solutions DNC relative to ∅ ′ shows that HT 2 = 2 implies RRT 2 2 , the Rainbow Ramsey Theorem for colorings of pairs for which there are most two pairs with each color, over RCA0 . The most interesting aspect of our construction of computable colorings as above is the use of an effective version of the Lovász Local Lemma due to Rumyantsev and Shen. Show more

Keywords: Reverse mathematics, Hindman’s Theorem, Lovász Local Lemma

DOI: 10.3233/COM-180094

Citation: Computability, vol. 8, no. 3-4, pp. 253-263, 2019

Authors: Fokina, Ekaterina | Rossegger, Dino | San Mauro, Luca

Article Type: Research Article

Abstract: Computable reducibility is a well-established notion that allows to compare the complexity of various equivalence relations over the natural numbers. We generalize computable reducibility by introducing degree spectra of reducibility and bi-reducibility. These spectra provide a natural way of measuring the complexity of reductions between equivalence relations. We prove that any upward closed collection of Turing degrees with a countable basis can be realised as a reducibility spectrum or as a bi-reducibility spectrum. We show also that there is a reducibility spectrum of computably enumerable equivalence relations with no countable basis and a reducibility spectrum of computably enumerable equivalence relations …which is downward dense, thus has no basis. Show more

Keywords: Computable structure theory, computable reducibility, computably enumerable equivalence relations, reducibility spectra

DOI: 10.3233/COM-180100

Citation: Computability, vol. 8, no. 3-4, pp. 265-280, 2019

Authors: Gherardi, Guido | Marcone, Alberto | Pauly, Arno

Article Type: Research Article

Abstract: In this paper we study, for n ⩾ 1 , the projection operators over R n , that is the multi-valued functions that associate to x ∈ R n and A ⊆ R n closed, the points of A which are closest to x . We also deal with approximate projections, where we content ourselves with points of A which are almost the closest to x . We use the tools of Weihrauch reducibility to classify these operators depending …on the representation of A and the dimension n . It turns out that, depending on the representation of the closed sets and the dimension of the space, the projection and approximate projection operators characterize some of the most fundamental computational classes in the Weihrauch lattice. Show more

Keywords: Projection operators, computable analysis, Weihrauch degrees

DOI: 10.3233/COM-180207

Citation: Computability, vol. 8, no. 3-4, pp. 281-304, 2019

Authors: Greenberg, Noam | Kuyper, Rutger | Turetsky, Dan

Article Type: Research Article

Abstract: We provide a survey of results using Weihrauch problems to find analogs between set theory and computability theory. In our treatment, we emphasize the role of morphisms in explaining these coincidences. We end with a discussion of the use of forcing to prove the nonexistence of morphisms.

Keywords: Cardinal invariants, Weihrauch reducibility, Turing degrees

DOI: 10.3233/COM-180219

Citation: Computability, vol. 8, no. 3-4, pp. 305-346, 2019

Authors: Harrison-Trainor, Matthew

Article Type: Research Article

Abstract: The class of Abelian p -groups are an example of some very interesting phenomena in computable structure theory. We will give an elementary first-order theory T p whose models are each bi-interpretable with the disjoint union of an Abelian p -group and a pure set (and so that every Abelian p -group is bi-interpretable with a model of T p ) using computable infinitary formulas. This answers a question of Knight by giving an example of an elementary first-order theory of “Ulm type”: Any two models, low for ω …1 C K , and with the same computable infinitary theory, are isomorphic. It also gives a new example of an elementary first-order theory whose isomorphism problem is Σ 1 1 -complete but not Borel complete. Show more

Keywords: p-groups, Borel reducibility, computable structure theory

DOI: 10.3233/COM-180099

Citation: Computability, vol. 8, no. 3-4, pp. 347-358, 2019

Authors: Harrison-Trainor, Matthew | Khoussainov, Bakh | Turetsky, Daniel

Article Type: Research Article

Abstract: In this paper we study various properties of algorithmically random infinite structures. Our results address the following questions. How would one define algorithmic randomness for infinite structures? Could algorithmically random structures be computable? What are the similarities and differences between algorithmically random structures and algorithmically random infinite strings? What are the possible Turing degrees of algorithmically random structures? Are there algorithmically random infinite groups? For instance, we prove the following in this paper: (1) there are classes which contain algorithmically random yet computable structures, (2) there exist algorithmically random universal algebras with co-computably enumerable as well as computably enumerable word problems, (3) there …are natural classes of structures in which the Turing degrees of algorithmically random structures can only be either computable or equivalent to the halting set, and (4) there are examples of algorithmically random groups. The first result shows a dramatic difference between algorithmically random strings and algorithmically random structures. The second result significantly improves the known theorem that algorithmically random structures computable in the halting set exist; these examples of algebras are sharp in terms of arithmetical hierarchy of the word problem for random algebras. The third result is a dichotomy theorem that characterises all possible Turing degrees of algorithmically random structures. Finally, the fourth result answers a nontrivial open question about the existence of algorithmically random groups. Show more

Keywords: Random structures, word problem, degree of a structure, random groups

DOI: 10.3233/COM-180101

Citation: Computability, vol. 8, no. 3-4, pp. 359-375, 2019

Authors: Kohlenbach, Ulrich

Article Type: Research Article

Abstract: The notion of ‘modulus of regularity’, as recently studied in [Moduli of regularity and rates of convergence for Fejér monotone sequences, 2017 , Preprint], unifies a number of different concepts used in convex optimization to establish rates of convergence for Fejér monotone iterative procedures. It generalizes the notion of ‘modulus of uniqueness’ to the nonunique case. In this paper, we investigate both notions in terms of reverse mathematics and calibrate their Weihrauch complexity.

Keywords: Moduli of regularity, moduli of uniqueness, reverse mathematics, Weihrauch complexity, convex optimization

DOI: 10.3233/COM-180097

Citation: Computability, vol. 8, no. 3-4, pp. 377-387, 2019