18 found
Sort by:
  1. Uri Andrews, Peter Gerdes & Joseph S. Miller (2014). The Degrees of Bi-Hyperhyperimmune Sets. Annals of Pure and Applied Logic 165 (3):803-811.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  2. Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller & André Nies (2014). Denjoy, Demuth and Density. Journal of Mathematical Logic 14 (1):1450004.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  3. Laurent Bienvenu & Joseph S. Miller (2012). Randomness and Lowness Notions Via Open Covers. Annals of Pure and Applied Logic 163 (5):506-518.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  4. Fernando J. Ferreira, John Harrison, François Loeser, Chris Miller, Joseph S. Miller, Slawomir J. Solecki, Stevo Todorcevic & John Steel (2010). Moscone Center West, San Francisco, CA January 15–16, 2010. Bulletin of Symbolic Logic 16 (3).
    Direct download  
     
    My bibliography  
     
    Export citation  
  5. Noam Greenberg & Joseph S. Miller (2009). Lowness for Kurtz Randomness. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  6. Joseph S. Miller (2009). The K -Degrees, Low for K Degrees,and Weakly Low for K Sets. 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)  
     
    My bibliography  
     
    Export citation  
  7. Rod Downey, Noam Greenberg & Joseph S. Miller (2008). The Upward Closure of a Perfect Thin Class. Annals of Pure and Applied Logic 156 (1):51-58.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  8. Verónica Becher, Santiago Figueira, Serge Grigorieff & Joseph S. Miller (2006). Randomness and Halting Probabilities. 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)  
     
    My bibliography  
     
    Export citation  
  9. Peter Cholak, Noam Greenberg & Joseph S. Miller (2006). Uniform Almost Everywhere Domination. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  10. Barbara F. Csima, Rod Downey, Noam Greenberg, Denis R. Hirschfeldt & Joseph S. Miller (2006). Every 1-Generic Computes a Properly 1-Generic. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  11. Rodney G. Downey, Carl Jockusch & Joseph S. Miller (2006). On Self-Embeddings of Computable Linear Orderings. Annals of Pure and Applied Logic 138 (1):52-76.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  12. Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann & Frank Stephan (2006). Kolmogorov–Loveland Randomness and Stochasticity. Annals of Pure and Applied Logic 138 (1):183-210.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  13. Joseph S. Miller & André Nies (2006). Randomness and Computability: Open Questions. Bulletin of Symbolic Logic 12 (3):390-410.
  14. Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller & André Nies (2005). Relativizing Chaitin's Halting Probability. Journal of Mathematical Logic 5 (02):167-192.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  15. Joseph S. Miller & Lawrence S. Moss (2005). The Undecidability of Iterated Modal Relativization. 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 (6 more)  
     
    My bibliography  
     
    Export citation  
  16. Joseph S. Miller (2004). Degrees of Unsolvability of Continuous Functions. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  17. Joseph S. Miller (2004). Every 2-Random Real is Kolmogorov Random. 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)  
     
    My bibliography  
     
    Export citation  
  18. Joseph S. Miller & Reed Solomon (2004). Effectiveness for Infinite Variable Words and the Dual Ramsey Theorem. 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 (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation