The Journal of Symbolic Logic (11)
Bulletin of Symbolic Logic (4)
Forum of Mathematics, Sigma (2)
Mathematical Proceedings of the Cambridge Philosophical Society (1)
Association for Symbolic Logic (15)
Forum of Mathematics (2)
Lecture Notes in Logic (6)
UNIFORM PROCEDURES IN UNCOUNTABLE STRUCTURES
NOAM GREENBERG, ALEXANDER G. MELNIKOV, JULIA F. KNIGHT, DANIEL TURETSKY
Journal: The Journal of Symbolic Logic / Volume 83 / Issue 2 / June 2018
This article contributes to the general program of extending techniques and ideas of effective algebra to computable metric space theory. It is well-known that relative computable categoricity (to be defined) of a computable algebraic structure is equivalent to having a c.e. Scott family with finitely many parameters (e.g., [1]). The first main result of the article extends this characterisation to computable Polish metric spaces. The second main result illustrates that just a slight change of the definitions will give us a new notion of categoricity unseen in the countable case (to be stated formally). The second result also shows that the characterisation of computably categorical closed subspaces of ${\Cal R}^n $ contained in [17] cannot be improved. The third main result extends the characterisation to not necessarily separable structures of cardinality κ using κ-computability.
STRONG JUMP-TRACEABILITY
NOAM GREENBERG, DAN TURETSKY
Journal: Bulletin of Symbolic Logic / Volume 24 / Issue 2 / June 2018
We review the current knowledge concerning strong jump-traceability. We cover the known results relating strong jump-traceability to randomness, and those relating it to degree theory. We also discuss the techniques used in working with strongly jump-traceable sets. We end with a section of open questions.
A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES
ROD DOWNEY, NOAM GREENBERG
Journal: Bulletin of Symbolic Logic / Volume 24 / Issue 1 / March 2018
Published online by Cambridge University Press: 26 April 2018, pp. 53-89
We introduce a new hierarchy of computably enumerable degrees. This hierarchy is based on computable ordinal notations measuring complexity of approximation of ${\rm{\Delta }}_2^0$ functions. The hierarchy unifies and classifies the combinatorics of a number of diverse constructions in computability theory. It does so along the lines of the high degrees (Martin) and the array noncomputable degrees (Downey, Jockusch, and Stob). The hierarchy also gives a number of natural definability results in the c.e. degrees, including a definable antichain.
HIGHER RANDOMNESS AND GENERICITY
NOAM GREENBERG, BENOIT MONIN
Journal: Forum of Mathematics, Sigma / Volume 5 / 2017
Published online by Cambridge University Press: 10 December 2017, e31
We use concepts of continuous higher randomness, developed in Bienvenu et al. ['Continuous higher randomness', J. Math. Log. 17(1) (2017).], to investigate $\unicode[STIX]{x1D6F1}_{1}^{1}$ -randomness. We discuss lowness for $\unicode[STIX]{x1D6F1}_{1}^{1}$ -randomness, cupping with $\unicode[STIX]{x1D6F1}_{1}^{1}$ -random sequences, and an analogue of the Hirschfeldt–Miller characterization of weak 2-randomness. We also consider analogous questions for Cohen forcing, concentrating on the class of $\unicode[STIX]{x1D6F4}_{1}^{1}$ -generic reals.
DNR AND INCOMPARABLE TURING DEGREES
MSC 2010: General logic
MSC 2010: Computability and recursion theory
MINZHONG CAI, NOAM GREENBERG, MICHAEL MCINERNEY
Published online by Cambridge University Press: 06 April 2016, e7
We construct an increasing ${\it\omega}$ -sequence $\langle \boldsymbol{a}_{n}\rangle$ of Turing degrees which forms an initial segment of the Turing degrees, and such that each $\boldsymbol{a}_{n+1}$ is diagonally nonrecursive relative to $\boldsymbol{a}_{n}$ . It follows that the DNR principle of reverse mathematics does not imply the existence of Turing incomparable degrees.
The finite intersection principle and genericity
DAVID DIAMONDSTONE, ROD DOWNEY, NOAM GREENBERG, DAN TURETSKY
Journal: Mathematical Proceedings of the Cambridge Philosophical Society / Volume 160 / Issue 2 / March 2016
We show that a Δ02 Turing degree computes solutions to all computable instances of the finite intersection principle if and only if it computes a 1-generic degree. We also investigate finite and infinite variants of the principle.
COMPUTABILITY AND UNCOUNTABLE LINEAR ORDERS II: DEGREE SPECTRA
NOAM GREENBERG, ASHER M. KACH, STEFFEN LEMPP, DANIEL D. TURETSKY
Journal: The Journal of Symbolic Logic / Volume 80 / Issue 1 / March 2015
We study the computable structure theory of linear orders of size $\aleph _1 $ within the framework of admissible computability theory. In particular, we study degree spectra and the successor relation.
COMPUTABILITY AND UNCOUNTABLE LINEAR ORDERS I: COMPUTABLE CATEGORICITY
We study the computable structure theory of linear orders of size $\aleph _1 $ within the framework of admissible computability theory. In particular, we characterize which of these linear orders are computably categorical.
CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS
LAURENT BIENVENU, ROD DOWNEY, NOAM GREENBERG, ANDRÉ NIES, DAN TURETSKY
We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15] (also Problem 5.5.19 in [34]). We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.
COMPUTING K-TRIVIAL SETS BY INCOMPLETE RANDOM SETS
LAURENT BIENVENU, ADAM R. DAY, NOAM GREENBERG, ANTONÍN KUČERA, JOSEPH S. MILLER, ANDRÉ NIES, DAN TURETSKY
Published online by Cambridge University Press: 13 May 2014, pp. 80-90
Every K-trivial set is computable from an incomplete Martin-Löf random set, i.e., a Martin-Löf random set that does not compute the halting problem.
Anti-Complex Sets and Reducibilities with Tiny Use
Johanna N. Y. Franklin, Noam Greenberg, Frank Stephan, Guohua Wu
Journal: The Journal of Symbolic Logic / Volume 78 / Issue 4 / December 2013
In contrast with the notion of complexity, a set A is called anti-complex if the Kolmogorov complexity of the initial segments of A chosen by a recursive function is always bounded by the identity function. We show that, as for complexity, the natural arena for examining anti-complexity is the weak-truth table degrees. In this context, we show the equivalence of anti-complexity and other lowness notions such as r.e. traceability or being weak truth-table reducible to a Schnorr trivial set. A set A is anti-complex if and only if it is reducible to another set B with tiny use, whereby we mean that the use function for reducing A to B can be made to grow arbitrarily slowly, as gauged by unbounded nondecreasing recursive functions. This notion of reducibility is then studied in its own right, and we also investigate its range and the range of its uniform counterpart.
Effective Mathematics of the Uncountable
Edited by Noam Greenberg, Denis Hirschfeldt, Joel David Hamkins, Russell Miller
Published online: 05 December 2013
Print publication: 31 October 2013
Buy the print book
Classical computable model theory is most naturally concerned with countable domains. There are, however, several methods – some old, some new – that have extended its basic concepts to uncountable structures. Unlike in the classical case, however, no single dominant approach has emerged, and different methods reveal different aspects of the computable content of uncountable mathematics. This book contains introductions to eight major approaches to computable uncountable mathematics: descriptive set theory; infinite time Turing machines; Blum-Shub-Smale computability; Sigma-definability; computability theory on admissible ordinals; E-recursion theory; local computability; and uncountable reverse mathematics. This book provides an authoritative and multifaceted introduction to this exciting new area of research that is still in its early stages. It is ideal as both an introductory text for graduate and advanced undergraduate students and a source of interesting new approaches for researchers in computability theory and related areas.
Edited by Noam Greenberg, Victoria University of Wellington, Denis Hirschfeldt, University of Chicago, Joel David Hamkins, College of Staten Island, Russell Miller, Queens College, City University of New York
Book: Effective Mathematics of the Uncountable
Print publication: 31 October 2013, pp vii-viii
Although classical computable model theory is most naturally concerned with countable domains, several methods – some old, some new – have extended its basic concepts to uncountable structures. Unlike in the classical case, however, no single dominant approach has emerged, and different methods reveal different aspects of the computable content of uncountable mathematics. Furthermore, uncountable computable model theory is still in an early stage of development, and, in particular, there has been relatively little work on connecting and comparing the various available approaches. Two Effective Mathematics of the Uncountable workshops were held at the CUNY Graduate Center in New York on August 18–22, 2008 and August 17–21, 2009, organized by Noam Greenberg, Joel Hamkins, Denis Hirschfeldt, and Russell Miller, with support from a Templeton Foundation "Exploring the Infinite" program grant. The aim of these workshops was to introduce a variety of approaches to uncountable computable model theory to researchers and students in computability theory and related fields, and to encourage collaboration between those who have developed and studied different facets of the effective content of uncountable mathematics.
Speaking at the EMU workshops were researchers with a wide range of backgrounds and motivations: Nate Ackerman, Wesley Calvert, Samuel Coskey, Noam Greenberg, Joel Hamkins, Denis Hirschfeldt, Julia Knight, Peter Koepke, David Linetsky, Robert Lubarsky, Russell Miller, Antonio Montalbán, Ansten Mørch Klev, Kerry Ojakian, Gerald Sacks, Richard Shore, Alexei Stukachev, and Philip Welch.
Print publication: 31 October 2013, pp v-vi
Print publication: 31 October 2013, pp 1-13
Chang and Keisler [8] famously defined model theory as the sum of logic and universal algebra. In the same spirit, one might describe computable model theory to be the investigation of the constraints on information content imposed by algebraic structure. The analogue of the interplay between syntactical objects and the algebraic structure they deine is the connection between deinability and complexity. One asks: How complicated are the constructions of model theory and algebra? What kind of information can be coded in structures like groups, ields, graphs, and orders? What mathematical distinctions are unearthed when "boldface" notions such as isomorphism are replaced by their "lightface" analogues such as, say, computable isomorphism?
A special case of the following definition was first rigorously made by Fröhlich and Shepherdson [11], following work of Hermann [17] and van der Waerden [40], which itself built on the constructive tradition of 19th century algebra. It was further developed by Rabin [32, 33] and Mal'cev [27].
Definition. Let ℒ be a computable signature (language), and let ℳ be an ℒ-structure whose universe is the set of natural numbers. The degree of ℳ is the Turing degree of the atomic (equivalently, quantifier-free) diagram of ℳ.
A structure is computable if its degree is 0, the Turing degree of computable sets. Equivalently, a structure ℳ is computable if, uniformly in the symbols of ℒ, the interpretations in ℳ of the constant symbols, function symbols, and relation symbols of ℒ are computable.
Print publication: 31 October 2013, pp i-iv
Computable structure theory using admissible recursion theory on ω1 using admissibility
By Noam Greenberg, Julia F. Knight
Print publication: 31 October 2013, pp 50-80
Abstract We use the theory of recursion on admissible ordinals to develop an analogue of classical computable model theory and effective algebra for structures of size ℵ1, which, under our assumptions, is equal to the continuum. We discuss both general concepts, such as computable categoricity, and particular classes of examples, such as fields and linear orderings.
§1. Introduction. Our aim is to develop computable structure theory for uncountable structures. In this paper we focus on structures of size ℵ1. The fundamental decision to be made, when trying to formulate such a theory, is the choice of computability tools that we intend to use. To discover which structures are computable, we need to first describe which subsets of the domain are computable, and which functions are computable. In this paper, we use admissible recursion theory (also known as α-recursion theory) over the domain ω1. We believe that this choice yields an interesting computable structure theory. It also illuminates the concepts and techniques of classical computable structure theory by observing similarities and differences between the countable and uncountable settings. In particular, it seems that as is the case for degree theory and for the study of the lattice of c.e. sets, the difference between true finiteness and its analogue in the generalised case, namely countability in our case, is fundamental to some constructions and reveals a deep gap between classical computability and attempts to generalise it to the realm of the uncountable.
A random set which only computes strongly jump-traceable c.e. sets
Noam Greenberg
We prove that there is a , 1-random set Y such that every computably enumerable set which is computable from Y is strongly jump-traceable.
We also show that for every order function h there is an ω-c.e. random set Y such that every computably enumerable set which is computable from Y is h-jump-traceable. This establishes a correspondence between rates of jump-traceability and computability from ω-c.e. random sets.
Benign cost functions and lowness properties
Noam Greenberg, André Nies
We show that the class of strongly jump-traceable c.e. sets can be characterised as those which have sufficiently slow enumerations so they obey a class of well-behaved cost functions, called benign. This characterisation implies the containment of the class of strongly jump-traceable c.e. Turing degrees in a number of lowness classes, in particular the classes of the degrees which lie below incomplete random degrees, indeed all LR-hard random degrees, and all ω-c.e. random degrees. The last result implies recent results of Diamondstone's and Ng's regarding cupping with superlow c.e. degrees and thus gives a use of algorithmic randomness in the study of the c.e. Turing degrees.
Lowness for Kurtz randomness
Noam Greenberg, Joseph S. Miller
We prove that degrees that are low for Kurtz randomness cannot be diagonally non-recursive. Together with the work of Stephan and Yu [16], this proves that they coincide with the hyperimmune-free non-DNR degrees, which are also exactly the degrees that are low for weak 1-genericity.
We also consider Low(ℳ, Kurtz), the class of degrees a such that every element of ℳ is a-Kurtz random. These are characterised when ℳ is the class of Martin-Löf random, computably random, or Schnorr random reals. We show that Low(ML, Kurtz) coincides with the non-DNR degrees, while both Low(CR, Kurtz) and Low(Schnorr, Kurtz) are exactly the non-high, non-DNR degrees.