Switch to: References

Add citations

You must login to add citations.
  1. Cone avoidance and randomness preservation.Stephen G. Simpson & Frank Stephan - 2015 - Annals of Pure and Applied Logic 166 (6):713-728.
  • A Nonstandard Counterpart of WWKL.Stephen G. Simpson & Keita Yokoyama - 2011 - Notre Dame Journal of Formal Logic 52 (3):229-243.
    In this paper, we introduce a system of nonstandard second-order arithmetic $\mathsf{ns}$-$\mathsf{WWKL_0}$ which consists of $\mathsf{ns}$-$\mathsf{BASIC}$ plus Loeb measure property. Then we show that $\mathsf{ns}$-$\mathsf{WWKL_0}$ is a conservative extension of $\mathsf{WWKL_0}$ and we do Reverse Mathematics for this system.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • Effectively closed sets of measures and randomness.Jan Reimann - 2008 - Annals of Pure and Applied Logic 156 (1):170-182.
    We show that if a real x2ω is strongly Hausdorff -random, where h is a dimension function corresponding to a convex order, then it is also random for a continuous probability measure μ such that the μ-measure of the basic open cylinders shrinks according to h. The proof uses a new method to construct measures, based on effective continuous transformations and a basis theorem for -classes applied to closed sets of probability measures. We use the main result to derive a (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  • The reverse mathematics of theorems of Jordan and lebesgue.André Nies, Marcus A. Triplett & Keita Yokoyama - 2021 - Journal of Symbolic Logic 86 (4):1657-1675.
    The Jordan decomposition theorem states that every function $f \colon \, [0,1] \to \mathbb {R}$ of bounded variation can be written as the difference of two non-decreasing functions. Combining this fact with a result of Lebesgue, every function of bounded variation is differentiable almost everywhere in the sense of Lebesgue measure. We analyze the strength of these theorems in the setting of reverse mathematics. Over $\mathsf {RCA}_{0}$, a stronger version of Jordan’s result where all functions are continuous is equivalent to (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • An Extension of van Lambalgen's Theorem to Infinitely Many Relative 1-Random Reals.Kenshi Miyabe - 2010 - Notre Dame Journal of Formal Logic 51 (3):337-349.
    Van Lambalgen's Theorem plays an important role in algorithmic randomness, especially when studying relative randomness. In this paper we extend van Lambalgen's Theorem by considering the join of infinitely many reals which are random relative to each other. In addition, we study computability of the reals in the range of Omega operators. It is known that $\Omega^{\phi'}$ is high. We extend this result to that $\Omega^{\phi^{(n)}}$ is $\textrm{high}_n$ . We also prove that there exists A such that, for each n (...)
    No categories
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • The K -Degrees, Low for K Degrees,and Weakly Low for K Sets.Joseph S. Miller - 2009 - Notre Dame Journal of Formal Logic 50 (4):381-391.
    We call A weakly low for K if there is a c such that $K^A(\sigma)\geq K(\sigma)-c$ for infinitely many σ; in other words, there are infinitely many strings that A does not help compress. We prove that A is weakly low for K if and only if Chaitin's Ω is A-random. This has consequences in the K-degrees and the low for K (i.e., low for random) degrees. Furthermore, we prove that the initial segment prefix-free complexity of 2-random reals is infinitely (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  • Randomness and computability: Open questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.
    It is time for a new paper about open questions in the currently very active area of randomness and computability. Ambos-Spies and Kučera presented such a paper in 1999 [1]. All the question in it have been solved, except for one: is KL-randomness different from Martin-Löf randomness? This question is discussed in Section 6.Not all the questions are necessarily hard—some simply have not been tried seriously. When we think a question is a major one, and therefore likely to be hard, (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   21 citations  
  • Propagation of partial randomness.Kojiro Higuchi, W. M. Phillip Hudelson, Stephen G. Simpson & Keita Yokoyama - 2014 - Annals of Pure and Applied Logic 165 (2):742-758.
    Let f be a computable function from finite sequences of 0ʼs and 1ʼs to real numbers. We prove that strong f-randomness implies strong f-randomness relative to a PA-degree. We also prove: if X is strongly f-random and Turing reducible to Y where Y is Martin-Löf random relative to Z, then X is strongly f-random relative to Z. In addition, we prove analogous propagation results for other notions of partial randomness, including non-K-triviality and autocomplexity. We prove that f-randomness relative to a (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • Defining a randomness notion via another.Kojiro Higuchi & Ningning Peng - 2014 - Mathematical Logic Quarterly 60 (4-5):280-288.
    To compare two randomness notions with each other, we ask whether a given randomness notion can be defined via another randomness notion. Inspired by Yu's pioneering study, we formalize our question using the concept of relativization of randomness. We give some solutions to our formalized questions. Also, our results include the affirmative answer to the problem asked by Yu in a discussion with the second author, i.e., whether Schnorr randomness relative to the halting problem is equivalent to Martin‐Löf randomness relative (...)
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • Two More Characterizations of K-Triviality.Noam Greenberg, Joseph S. Miller, Benoit Monin & Daniel Turetsky - 2018 - Notre Dame Journal of Formal Logic 59 (2):189-195.
    We give two new characterizations of K-triviality. We show that if for all Y such that Ω is Y-random, Ω is -random, then A is K-trivial. The other direction was proved by Stephan and Yu, giving us the first titular characterization of K-triviality and answering a question of Yu. We also prove that if A is K-trivial, then for all Y such that Ω is Y-random, ≡LRY. This answers a question of Merkle and Yu. The other direction is immediate, so (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  • Pa Relative to an Enumeration Oracle.G. O. H. Jun Le, Iskander Sh Kalimullin, Joseph S. Miller & Mariya I. Soskova - 2023 - Journal of Symbolic Logic 88 (4):1497-1525.
    Recall that B is PA relative to A if B computes a member of every nonempty $\Pi ^0_1(A)$ class. This two-place relation is invariant under Turing equivalence and so can be thought of as a binary relation on Turing degrees. Miller and Soskova [23] introduced the notion of a $\Pi ^0_1$ class relative to an enumeration oracle A, which they called a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. We study the induced extension of the relation B is PA relative (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • Lowness properties and approximations of the jump.Santiago Figueira, André Nies & Frank Stephan - 2008 - Annals of Pure and Applied Logic 152 (1):51-66.
    We study and compare two combinatorial lowness notions: strong jump-traceability and well-approximability of the jump, by strengthening the notion of jump-traceability and super-lowness for sets of natural numbers. A computable non-decreasing unbounded function h is called an order function. Informally, a set A is strongly jump-traceable if for each order function h, for each input e one may effectively enumerate a set Te of possible values for the jump JA, and the number of values enumerated is at most h. A′ (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  • Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
    The stable Ramsey's theorem for pairs has been the subject of numerous investigations in mathematical logic. We introduce a weaker form of it by restricting from the class of all stable colorings to subclasses of it that are nonnull in a certain effective measure-theoretic sense. We show that the sets that can compute infinite homogeneous sets for nonnull many computable stable colorings and the sets that can compute infinite homogeneous sets for all computable stable colorings agree below $\emptyset'$ but not (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Calibrating randomness.Rod Downey, Denis R. Hirschfeldt, André Nies & Sebastiaan A. Terwijn - 2006 - Bulletin of Symbolic Logic 12 (3):411-491.
    We report on some recent work centered on attempts to understand when one set is more random than another. We look at various methods of calibration by initial segment complexity, such as those introduced by Solovay [125], Downey, Hirschfeldt, and Nies [39], Downey, Hirschfeldt, and LaForte [36], and Downey [31]; as well as other methods such as lowness notions of Kučera and Terwijn [71], Terwijn and Zambella [133], Nies [101, 100], and Downey, Griffiths, and Reid [34]; higher level randomness notions (...)
    Direct download (11 more)  
     
    Export citation  
     
    Bookmark   29 citations  
  • The axiomatic power of Kolmogorov complexity.Laurent Bienvenu, Andrei Romashchenko, Alexander Shen, Antoine Taveneaux & Stijn Vermeeren - 2014 - Annals of Pure and Applied Logic 165 (9):1380-1402.
    The famous Gödel incompleteness theorem states that for every consistent, recursive, and sufficiently rich formal theory T there exist true statements that are unprovable in T . Such statements would be natural candidates for being added as axioms, but how can we obtain them? One classical approach is to add to some theory T an axiom that claims the consistency of T . In this paper we discuss another approach motivated by Chaitin's version of Gödel's theorem where axioms claiming the (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark  
  • 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 (6 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • Π 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 (4 more)  
     
    Export citation  
     
    Bookmark   10 citations