22 found
Order:
  1. Effectiveness for Infinite Variable Words and the Dual Ramsey Theorem.Joseph S. Miller & Reed Solomon - 2004 - Archive for Mathematical Logic 43 (4):543-555.
    We examine the Dual Ramsey Theorem and two related combinatorial principles VW(k,l) and OVW(k,l) from the perspectives of reverse mathematics and effective mathematics. We give a statement of the Dual Ramsey Theorem for open colorings in second order arithmetic and formalize work of Carlson and Simpson [1] to show that this statement implies ACA 0 over RCA 0 . We show that neither VW(2,2) nor OVW(2,2) is provable in WKL 0 . These results give partial answers to questions posed by (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  2.  25
    Randomness and Computability: Open Questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.
  3. Universal Computably Enumerable Equivalence Relations.Uri Andrews, Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Luca San Mauro & Andrea Sorbi - 2014 - Journal of Symbolic Logic 79 (1):60-88.
  4. Every 2-Random Real is Kolmogorov Random.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (3):907-913.
    We study reals with infinitely many incompressible prefixes. Call $A \in 2^{\omega}$ Kolmogorot random if $(\exists^{\infty}n) C(A \upharpoonright n) \textgreater n - \mathcal{O}(1)$ , where C denotes plain Kolmogorov complexity. This property was suggested by Loveland and studied by $Martin-L\ddot{0}f$ , Schnorr and Solovay. We prove that 2-random reals are Kolmogorov random. Together with the converse-proved by Nies. Stephan and Terwijn [11]-this provides a natural characterization of 2-randomness in terms of plain complexity. We finish with a related characterization of 2-randomness.
    Direct download (8 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  5.  5
    Relativizing Chaitin's Halting Probability.Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller & André Nies - 2005 - Journal of Mathematical Logic 5 (02):167-192.
  6. 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 - 2014 - Bulletin of Symbolic Logic 20 (1):80-90.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  7.  2
    Kolmogorov–Loveland Randomness and Stochasticity.Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann & Frank Stephan - 2006 - Annals of Pure and Applied Logic 138 (1):183-210.
    An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL-randomness. Our first (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   7 citations  
  8.  16
    Lowness for Kurtz Randomness.Noam Greenberg & Joseph S. Miller - 2009 - Journal of Symbolic Logic 74 (2):665-678.
    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(M, Kurtz), the class of degrees a such that every element of M is a-Kurtz random. These are characterised when M is the class of Martin-Löf random, computably random, or Schnorr random reals. (...)
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  9.  13
    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 (4 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  10.  1
    Randomness and Lowness Notions Via Open Covers.Laurent Bienvenu & Joseph S. Miller - 2012 - Annals of Pure and Applied Logic 163 (5):506-518.
  11.  1
    Denjoy, Demuth and Density.Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller & André Nies - 2014 - Journal of Mathematical Logic 14 (1):1450004.
  12.  12
    Uniform Almost Everywhere Domination.Peter Cholak, Noam Greenberg & Joseph S. Miller - 2006 - Journal of Symbolic Logic 71 (3):1057 - 1072.
    We explore the interaction between Lebesgue measure and dominating functions. We show, via both a priority construction and a forcing construction, that there is a function of incomplete degree that dominates almost all degrees. This answers a question of Dobrinen and Simpson, who showed that such functions are related to the proof-theoretic strength of the regularity of Lebesgue measure for Gδ sets. Our constructions essentially settle the reverse mathematical classification of this principle.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  13.  13
    Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
    We show that the Turing degrees are not sufficient to measure the complexity of continuous functions on [0, 1]. Computability of continuous real functions is a standard notion from computable analysis. However, no satisfactory theory of degrees of continuous functions exists. We introduce the continuous degrees and prove that they are a proper extension of the Turing degrees and a proper substructure of the enumeration degrees. Call continuous degrees which are not Turing degrees non-total. Several fundamental results are proved: a (...)
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  14.  12
    The Undecidability of Iterated Modal Relativization.Joseph S. Miller & Lawrence S. Moss - 2005 - Studia Logica 79 (3):373-407.
    In dynamic epistemic logic and other fields, it is natural to consider relativization as an operator taking sentences to sentences. When using the ideas and methods of dynamic logic, one would like to iterate operators. This leads to iterated relativization. We are also concerned with the transitive closure operation, due to its connection to common knowledge. We show that for three fragments of the logic of iterated relativization and transitive closure, the satisfiability problems are fi1 11–complete. Two of these fragments (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  15.  3
    On Self-Embeddings of Computable Linear Orderings.Rodney G. Downey, Carl Jockusch & Joseph S. Miller - 2006 - Annals of Pure and Applied Logic 138 (1):52-76.
    The Dushnik–Miller Theorem states that every infinite countable linear ordering has a nontrivial self-embedding. We examine computability-theoretical aspects of this classical theorem.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  16.  20
    Every 1-Generic Computes a Properly 1-Generic.Barbara F. Csima, Rod Downey, Noam Greenberg, Denis R. Hirschfeldt & Joseph S. Miller - 2006 - Journal of Symbolic Logic 71 (4):1385 - 1393.
    A real is called properly n-generic if it is n-generic but not n+1-generic. We show that every 1-generic real computes a properly 1-generic real. On the other hand, if m > n ≥ 2 then an m-generic real cannot compute a properly n-generic real.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  17.  1
    Nullifying Randomness and Genericity Using Symmetric Difference.Rutger Kuyper & Joseph S. Miller - 2017 - Annals of Pure and Applied Logic 168 (9):1692-1699.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  18.  4
    The Degrees of Bi-Hyperhyperimmune Sets.Uri Andrews, Peter Gerdes & Joseph S. Miller - 2014 - Annals of Pure and Applied Logic 165 (3):803-811.
    We study the degrees of bi-hyperhyperimmune sets. Our main result characterizes these degrees as those that compute a function that is not dominated by any ∆02 function, and equivalently, those that compute a weak 2-generic. These characterizations imply that the collection of bi-hhi Turing degrees is closed upwards.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  19.  9
    Randomness and Halting Probabilities.Verónica Becher, Santiago Figueira, Serge Grigorieff & Joseph S. Miller - 2006 - Journal of Symbolic Logic 71 (4):1411 - 1430.
    We consider the question of randomness of the probability ΩU[X] that an optimal Turing machine U halts and outputs a string in a fixed set X. The main results are as follows: ΩU[X] is random whenever X is $\Sigma _{n}^{0}$-complete or $\Pi _{n}^{0}$-complete for some n ≥ 2. However, for n ≥ 2, ΩU[X] is not n-random when X is $\Sigma _{n}^{0}$ or $\Pi _{n}^{0}$ Nevertheless, there exists $\Delta _{n+1}^{0}$ sets such that ΩU[X] is n-random. There are $\Delta _{2}^{0}$ sets (...)
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  20.  2
    Moscone Center West, San Francisco, CA January 15–16, 2010.Fernando J. Ferreira, John Harrison, François Loeser, Chris Miller, Joseph S. Miller, Slawomir J. Solecki, Stevo Todorcevic & John Steel - 2010 - Bulletin of Symbolic Logic 16 (3).
    Direct download  
     
    Export citation  
     
    My bibliography  
  21. The Upward Closure of a Perfect Thin Class.Rod Downey, Noam Greenberg & Joseph S. Miller - 2008 - Annals of Pure and Applied Logic 156 (1):51-58.
    There is a perfect thin class whose upward closure in the Turing degrees has full measure . Thus, in the Muchnik lattice of classes, the degree of 2-random reals is comparable with the degree of some perfect thin class. This solves a question of Simpson [S. Simpson, Mass problems and randomness, Bulletin of Symbolic Logic 11 1–27].
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  22. Lowness for Effective Hausdorff Dimension.Steffen Lempp, Joseph S. Miller, Keng Meng Ng, Daniel D. Turetsky & Rebecca Weber - 2014 - Journal of Mathematical Logic 14 (2):1450011.