32 found
Order:
  1. The ibT Degrees of Computably Enumerable Sets Are Not Dense.George Barmpalias & Andrew E. M. Lewis - 2006 - Annals of Pure and Applied Logic 141 (1-2):51-60.
    We show that the identity bounded Turing degrees of computably enumerable sets are not dense.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   7 citations  
  2.  6
    Π 1 0 Classes, L R Degrees and Turing Degrees.George Barmpalias, Andrew E. M. Lewis & Frank Stephan - 2008 - Annals of Pure and Applied Logic 156 (1):21-38.
    We say that A≤LRB if every B-random set is A-random with respect to Martin–Löf randomness. We study this relation and its interactions with Turing reducibility, classes, hyperimmunity and other recursion theoretic notions.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  3.  12
    Randomness, Lowness and Degrees.George Barmpalias, Andrew E. M. Lewis & Mariya Soskova - 2008 - Journal of Symbolic Logic 73 (2):559 - 577.
    We say that A ≤LR B if every B-random number is A-random. Intuitively this means that if oracle A can identify some patterns on some real γ. In other words. B is at least as good as A for this purpose. We study the structure of the LR degrees globally and locally (i.e., restricted to the computably enumberable degrees) and their relationship with the Turing degrees. Among other results we show that whenever α in not GL₂ the LR degree of (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  4.  22
    A C.E. Real That Cannot Be SW-Computed by Any Ω Number.George Barmpalias & Andrew E. M. Lewis - 2006 - Notre Dame Journal of Formal Logic 47 (2):197-209.
    The strong weak truth table (sw) reducibility was suggested by Downey, Hirschfeldt, and LaForte as a measure of relative randomness, alternative to the Solovay reducibility. It also occurs naturally in proofs in classical computability theory as well as in the recent work of Soare, Nabutovsky, and Weinberger on applications of computability to differential geometry. We study the sw-degrees of c.e. reals and construct a c.e. real which has no random c.e. real (i.e., Ω number) sw-above it.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   5 citations  
  5.  2
    Classes, LR Degrees and Turing Degrees.George Barmpalias, Andrew Lewis & Frank Stephan - 2008 - Annals of Pure and Applied Logic 156 (1):21-38.
    We say that A≤LRB if every B-random set is A-random with respect to Martin–Löf randomness. We study this relation and its interactions with Turing reducibility, classes, hyperimmunity and other recursion theoretic notions.
    Direct download  
     
    Export citation  
     
    My bibliography   4 citations  
  6.  21
    The Importance of Π⁰₁ Classes in Effective Randomness.George Barmpalias, Andrew E. M. Lewis & Keng Meng Ng - 2010 - Journal of Symbolic Logic 75 (1):387-400.
    We prove a number of results in effective randomness, using methods in which $\Pi _{1}^{0}$ classes play an essential role. The results proved include the fact that every PA Turing degree is the join of two random Turing degrees, and the existence of a minimal pair of LR degrees below the LR degree of the halting problem.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  7.  3
    The Importance of Π1 0 Classes in Effective Randomness.George Barmpalias, Andrew E. M. Lewis & Keng Meng Ng - 2010 - Journal of Symbolic Logic 75 (1):387-400.
    We prove a number of results in effective randomness, using methods in which Π⁰₁ classes play an essential role. The results proved include the fact that every PA Turing degree is the join of two random Turing degrees, and the existence of a minimal pair of LR degrees below the LR degree of the halting problem.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  8.  19
    Elementary Differences Between the Degrees of Unsolvability and Degrees of Compressibility.George Barmpalias - 2010 - Annals of Pure and Applied Logic 161 (7):923-934.
    Given two infinite binary sequences A,B we say that B can compress at least as well as A if the prefix-free Kolmogorov complexity relative to B of any binary string is at most as much as the prefix-free Kolmogorov complexity relative to A, modulo a constant. This relation, introduced in Nies [14] and denoted by A≤LKB, is a measure of relative compressing power of oracles, in the same way that Turing reducibility is a measure of relative information. The equivalence classes (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  9.  19
    Algorithmic Randomness and Measures of Complexity.George Barmpalias - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
    We survey recent advances on the interface between computability theory and algorithmic randomness, with special attention on measures of relative complexity. We focus on (weak) reducibilities that measure (a) the initial segment complexity of reals and (b) the power of reals to compress strings, when they are used as oracles. The results are put into context and several connections are made with various central issues in modern algorithmic randomness and computability.
    Direct download  
     
    Export citation  
     
    My bibliography   1 citation  
  10. Algorithmic Randomness and Measures of Complexity.George Barmpalias - 2013 - Bulletin of Symbolic Logic 19 (3):318-350.
  11.  13
    Hypersimplicity and Semicomputability in the Weak Truth Table Degrees.George Barmpalias - 2005 - Archive for Mathematical Logic 44 (8):1045-1065.
  12.  1
    Randomness and the Linear Degrees of Computability.Andrew Em Lewis & George Barmpalias - 2007 - Annals of Pure and Applied Logic 145 (3):252-257.
    We show that there exists a real α such that, for all reals β, if α is linear reducible to β then β≤Tα. In fact, every random real satisfies this quasi-maximality property. As a corollary we may conclude that there exists no ℓ-complete Δ2 real. Upon realizing that quasi-maximality does not characterize the random reals–there exist reals which are not random but which are of quasi-maximal ℓ-degree–it is then natural to ask whether maximality could provide such a characterization. Such hopes, (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  13.  21
    Relative Randomness and Cardinality.George Barmpalias - 2010 - Notre Dame Journal of Formal Logic 51 (2):195-205.
    A set $B\subseteq\mathbb{N}$ is called low for Martin-Löf random if every Martin-Löf random set is also Martin-Löf random relative to B . We show that a $\Delta^0_2$ set B is low for Martin-Löf random if and only if the class of oracles which compress less efficiently than B , namely, the class $\mathcal{C}^B=\{A\ |\ \forall n\ K^B(n)\leq^+ K^A(n)\}$ is countable (where K denotes the prefix-free complexity and $\leq^+$ denotes inequality modulo a constant. It follows that $\Delta^0_2$ is the largest arithmetical (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  14.  10
    Algorithmic Randomness of Continuous Functions.George Barmpalias, Paul Brodhead, Douglas Cenzer, Jeffrey B. Remmel & Rebecca Weber - 2008 - Archive for Mathematical Logic 46 (7-8):533-546.
    We investigate notions of randomness in the space ${{\mathcal C}(2^{\mathbb N})}$ of continuous functions on ${2^{\mathbb N}}$ . A probability measure is given and a version of the Martin-Löf test for randomness is defined. Random ${\Delta^0_2}$ continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any ${y \in 2^{\mathbb N}}$ , (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  15.  32
    H‐Monotonically Computable Real Numbers.Xizhong Zheng, Robert Rettinger & George Barmpalias - 2005 - Mathematical Logic Quarterly 51 (2):157-170.
    Let h : ℕ → ℚ be a computable function. A real number x is called h-monotonically computable if there is a computable sequence of rational numbers which converges to x h-monotonically in the sense that h|x – xn| ≥ |x – xm| for all n andm > n. In this paper we investigate classes h-MC of h-mc real numbers for different computable functions h. Especially, for computable functions h : ℕ → ℚ, we show that the class h-MC coincides (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  16.  11
    A Transfinite Hierarchy of Reals.George Barmpalias - 2003 - Mathematical Logic Quarterly 49 (2):163-172.
    We extend the hierarchy defined in [5] to cover all hyperarithmetical reals. An intuitive idea is used or the definition, but a characterization of the related classes is obtained. A hierarchy theorem and two fixed point theorems are presented.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  17.  15
    The Approximation Structure of a Computably Approximable Real.George Barmpalias - 2003 - Journal of Symbolic Logic 68 (3):885-922.
    A new approach for a uniform classification of the computably approximable real numbers is introduced. This is an important class of reals, consisting of the limits of computable sequences of rationals, and it coincides with the 0'-computable reals. Unlike some of the existing approaches, this applies uniformly to all reals in this class: to each computably approximable real x we assign a degree structure, the structure of all possible ways available to approximate x. So the main criterion for such classification (...)
    Direct download (9 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  18.  32
    The Http://Ars. Els-Cdn. Com/Content/Image/Http://Origin-Ars. Els-Cdn. Com/Content/Image/1-S2. 0-S0168007205001429-Si1. Gif"/> Degrees of Computably Enumerable Sets Are Not Dense. [REVIEW]George Barmpalias & Andrew Em Lewis - 2006 - Annals of Pure and Applied Logic 141 (1):51-60.
  19.  21
    On the Existence of a Strong Minimal Pair.George Barmpalias, Mingzhong Cai, Steffen Lempp & Theodore A. Slaman - 2015 - Journal of Mathematical Logic 15 (1):1550003.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  20.  17
    Approximation Representations for Δ2 Reals.George Barmpalias - 2004 - Archive for Mathematical Logic 43 (8):947-964.
    We study Δ2 reals x in terms of how they can be approximated symmetrically by a computable sequence of rationals. We deal with a natural notion of ‘approximation representation’ and study how these are related computationally for a fixed x. This is a continuation of earlier work; it aims at a classification of Δ2 reals based on approximation and it turns out to be quite different than the existing ones (based on information content etc.).
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  21.  11
    Approximation Representations for Reals and Their Wtt-Degrees.George Barmpalias - 2004 - Mathematical Logic Quarterly 50 (45):370-380.
    We study the approximation properties of computably enumerable reals. We deal with a natural notion of approximation representation and study their wtt-degrees. Also, we show that a single representation may correspond to a quite diverse variety of reals.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  22.  17
    The Hypersimple-Free C.E. WTT Degrees Are Dense in the C.E. WTT Degrees.George Barmpalias & Andrew E. M. Lewis - 2006 - Notre Dame Journal of Formal Logic 47 (3):361-370.
    We show that in the c.e. weak truth table degrees if b < c then there is an a which contains no hypersimple set and b < a < c. We also show that for every w < c in the c.e. wtt degrees such that w is hypersimple, there is a hypersimple a such that w < a < c. On the other hand, we know that there are intervals which contain no hypersimple set.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  23.  12
    Upper Bounds on Ideals in the Computably Enumerable Turing Degrees.George Barmpalias & André Nies - 2011 - Annals of Pure and Applied Logic 162 (6):465-473.
    We study ideals in the computably enumerable Turing degrees, and their upper bounds. Every proper ideal in the c.e. Turing degrees has an incomplete upper bound. It follows that there is no prime ideal in the c.e. Turing degrees. This answers a question of Calhoun [2]. Every proper ideal in the c.e. Turing degrees has a low2 upper bound. Furthermore, the partial order of ideals under inclusion is dense.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  24.  11
    Tracing and Domination in the Turing Degrees.George Barmpalias - 2012 - Annals of Pure and Applied Logic 163 (5):500-505.
  25.  7
    Jump Inversions Inside Effectively Closed Sets and Applications to Randomness.George Barmpalias, Rod Downey & Keng Meng Ng - 2011 - Journal of Symbolic Logic 76 (2):491 - 518.
    We study inversions of the jump operator on ${\mathrm{\Pi }}_{1}^{0}$ classes, combined with certain basis theorems. These jump inversions have implications for the study of the jump operator on the random degrees—for various notions of randomness. For example, we characterize the jumps of the weakly 2-random sets which are not 2-random, and the jumps of the weakly 1-random relative to 0′ sets which are not 2-random. Both of the classes coincide with the degrees above 0′ which are not 0′-dominated. A (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  26.  8
    Barcelona, Catalonia, Spain July 11–16, 2011.Georges Gonthier, Martin Ziegler, Steve Awodey, George Barmpalias & Lev D. Beklemishev - 2012 - Bulletin of Symbolic Logic 18 (3).
    Direct download  
     
    Export citation  
     
    My bibliography  
  27.  6
    Kolmogorov Complexity and Computably Enumerable Sets.George Barmpalias & Angsheng Li - 2013 - Annals of Pure and Applied Logic 164 (12):1187-1200.
  28.  5
    Http://Ars. Els-Cdn. Com/Content/Image/Http://Origin-Ars. Els-Cdn. Com/Content/Image/1-S2. 0-S0168007208000821-Si1. Gif"/> Classes, LR Degrees and Turing Degrees. [REVIEW]George Barmpalias, Andrew Em Lewis & Frank Stephan - 2008 - Annals of Pure and Applied Logic 156 (1):21-38.
  29.  1
    Exact Pairs for the Ideal of the K-Trivial Sequences in the Turing Degrees.George Barmpalias & Rod G. Downey - 2014 - Journal of Symbolic Logic 79 (3):676-692.
  30.  1
    Isaac Newton Institute, Cambridge, UK July 2–6, 2012.George Barmpalias, Vasco Brattka, Adam Day, Rod Downey, John Hitchcock, Michal Koucký, Andy Lewis, Jack Lutz, André Nies & Alexander Shen - 2013 - Bulletin of Symbolic Logic 19 (1).
    Direct download  
     
    Export citation  
     
    My bibliography  
  31. M. Lerman, A Framework for Priority Arguments.George Barmpalias - 2011 - Bulletin of Symbolic Logic 17 (3):464.
     
    Export citation  
     
    My bibliography  
  32. The Importance of $\Pi _1^0$ Classes in Effective Randomness. The Journal of Symbolic Logic, Vol. 75.George Barmpalias, Andrew E. M. Lewis, Keng Meng Ng & Frank Stephan - 2012 - Bulletin of Symbolic Logic 18 (3):409-412.