26 found
Sort by:
  1. George Barmpalias (forthcoming). Algorithmic Randomness and Measures of Complexity. 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.
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  2. George Barmpalias, Andrew E. M. Lewis & Mariya Soskova (forthcoming). Randomness, Lowness and Degrees. Journal of Symbolic Logic.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  3. George Barmpalias, Vasco Brattka, Adam Day, Rod Downey, John Hitchcock, Michal Koucký, Andy Lewis, Jack Lutz, André Nies & Alexander Shen (2013). Isaac Newton Institute, Cambridge, UK July 2–6, 2012. Bulletin of Symbolic Logic 19 (1).
    Direct download  
     
    My bibliography  
     
    Export citation  
  4. George Barmpalias & Angsheng Li (2013). Kolmogorov Complexity and Computably Enumerable Sets. Annals of Pure and Applied Logic 164 (12):1187-1200.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  5. George Barmpalias (2012). Tracing and Domination in the Turing Degrees. Annals of Pure and Applied Logic 163 (5):500-505.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6. Georges Gonthier, Martin Ziegler, Steve Awodey, George Barmpalias & Lev D. Beklemishev (2012). Barcelona, Catalonia, Spain July 11–16, 2011. Bulletin of Symbolic Logic 18 (3).
    Direct download  
     
    My bibliography  
     
    Export citation  
  7. George Barmpalias (2011). M. Lerman, A Framework for Priority Arguments. Bulletin of Symbolic Logic 17 (3):464.
     
    My bibliography  
     
    Export citation  
  8. George Barmpalias, Rod Downey & Keng Meng Ng (2011). Jump Inversions Inside Effectively Closed Sets and Applications to Randomness. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  9. George Barmpalias & André Nies (2011). Upper Bounds on Ideals in the Computably Enumerable Turing Degrees. Annals of Pure and Applied Logic 162 (6):465-473.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  10. George Barmpalias (2010). Elementary Differences Between the Degrees of Unsolvability and Degrees of Compressibility. Annals of Pure and Applied Logic 161 (7):923-934.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  11. George Barmpalias (2010). Relative Randomness and Cardinality. 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)  
     
    My bibliography  
     
    Export citation  
  12. George Barmpalias, Andrew E. M. Lewis & Keng Meng Ng (2010). The Importance of Π⁰₁ Classes in Effective Randomness. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  13. George Barmpalias, Paul Brodhead, Douglas Cenzer, Jeffrey B. Remmel & Rebecca Weber (2008). Algorithmic Randomness of Continuous Functions. 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}}$ , (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  14. George Barmpalias, Andrew E. M. Lewis & Mariya Soskova (2008). Randomness, Lowness and Degrees. 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 (3 more)  
     
    My bibliography  
     
    Export citation  
  15. George Barmpalias, Andrew E. M. Lewis & Frank Stephan (2008). Classes, Degrees and Turing Degrees. Annals of Pure and Applied Logic 156 (1):21-38.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  16. George Barmpalias, Andrew Em Lewis & Frank Stephan (2008). 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] Annals of Pure and Applied Logic 156 (1):21-38.
    Direct download  
     
    My bibliography  
     
    Export citation  
  17. Andrew Em Lewis & George Barmpalias (2007). Randomness and the Linear Degrees of Computability. Annals of Pure and Applied Logic 145 (3):252-257.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  18. George Barmpalias & Andrew E. M. Lewis (2006). The Degrees of Computably Enumerable Sets Are Not Dense. Annals of Pure and Applied Logic 141 (1-2):51-60.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  19. George Barmpalias & Andrew E. M. Lewis (2006). A C.E. Real That Cannot Be SW-Computed by Any Ω Number. 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)  
     
    My bibliography  
     
    Export citation  
  20. George Barmpalias & Andrew E. M. Lewis (2006). The Hypersimple-Free C.E. WTT Degrees Are Dense in the C.E. WTT Degrees. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  21. George Barmpalias & Andrew Em Lewis (2006). 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] Annals of Pure and Applied Logic 141 (1):51-60.
    Direct download  
     
    My bibliography  
     
    Export citation  
  22. George Barmpalias (2005). Hypersimplicity and Semicomputability in the Weak Truth Table Degrees. Archive for Mathematical Logic 44 (8):1045-1065.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  23. Xizhong Zheng, Robert Rettinger & George Barmpalias (2005). H‐Monotonically Computable Real Numbers. Mathematical Logic Quarterly 51 (2):157-170.
    No categories
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  24. George Barmpalias (2004). Approximation Representations for Δ2 Reals. 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.).
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  25. George Barmpalias (2003). A Transfinite Hierarchy of Reals. Mathematical Logic Quarterly 49 (2):163-172.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  26. George Barmpalias (2003). The Approximation Structure of a Computably Approximable Real. 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 (8 more)  
     
    My bibliography  
     
    Export citation