Switch to: References

Add citations

You must login to add citations.
  1. The nature of probability.Patrick Suppes - 2010 - Philosophical Studies 147 (1):89 - 102.
    The thesis of this article is that the nature of probability is centered on its formal properties, not on any of its standard interpretations. Section 2 is a survey of Bayesian applications. Section 3 focuses on two examples from physics that seem as completely objective as other physical concepts. Section 4 compares the conflict between subjective Bayesians and objectivists about probability to the earlier strident conflict in physics about the nature of force. Section 5 outlines a pragmatic approach to the (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Recognizing strong random reals.Daniel Osherson - 2008 - Review of Symbolic Logic 1 (1):56-63.
    1. Characterizing randomness. Consider a physical process that, if suitably idealized, generates an indefinite sequence of independent random bits. One such process might be radioactive decay of a lump of uranium whose mass is kept at just the level needed to ensure that the probability is one-half that no alpha particle is emitted in the nth microsecond of the experiment. Let us think of the bits as drawn from {0, 1} and denote the resulting sequence by x with coordinates x0, (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   4 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  
  • 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 (4 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  • Randomness? What Randomness?Klaas Landsman - 2020 - Foundations of Physics 50 (2):61-104.
    This is a review of the issue of randomness in quantum mechanics, with special emphasis on its ambiguity; for example, randomness has different antipodal relationships to determinism, computability, and compressibility. Following a philosophical discussion of randomness in general, I argue that deterministic interpretations of quantum mechanics are strictly speaking incompatible with the Born rule. I also stress the role of outliers, i.e. measurement outcomes that are not 1-random. Although these occur with low probability, their very existence implies that the no-signaling (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Does truth-table of linear norm reduce the one-query tautologies to a random oracle?Masahiro Kumabe, Toshio Suzuki & Takeshi Yamazaki - 2008 - Archive for Mathematical Logic 47 (2):159-180.
    In our former works, for a given concept of reduction, we study the following hypothesis: “For a random oracle A, with probability one, the degree of the one-query tautologies with respect to A is strictly higher than the degree of A.” In our former works (Suzuki in Kobe J. Math. 15, 91–102, 1998; in Inf. Comput. 176, 66–87, 2002; in Arch. Math. Logic 44, 751–762), the following three results are shown: The hypothesis for p-T (polynomial-time Turing) reduction is equivalent to (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  • Low upper bounds of ideals.Antonín Kučera & Theodore A. Slaman - 2009 - Journal of Symbolic Logic 74 (2):517-534.
    We show that there is a low T-upper bound for the class of K-trivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in $\Delta _2^0 $ T-degrees for which there is a low T-upper bound.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • 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  
     
    Bookmark   9 citations  
  • Schnorr triviality and genericity.Johanna N. Y. Franklin - 2010 - Journal of Symbolic Logic 75 (1):191-207.
    We study the connection between Schnorr triviality and genericity. We show that while no 2-generic is Turing equivalent to a Schnorr trivial and no 1-generic is tt-equivalent to a Schnorr trivial, there is a 1-generic that is Turing equivalent to a Schnorr trivial. However, every such 1-generic must be high. As a corollary, we prove that not all K-trivials are Schnorr trivial. We also use these techniques to extend a previous result and show that the bases of cones of Schnorr (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  • Schnorr trivial reals: a construction. [REVIEW]Johanna N. Y. Franklin - 2008 - Archive for Mathematical Logic 46 (7-8):665-678.
    A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null ${\Sigma^0_1}$ (recursive) class of reals. Although these randomness notions are very closely related, the set of Turing degrees containing reals that are K-trivial has very different properties from the set of Turing degrees that are Schnorr trivial. Nies proved in (Adv Math 197(1):274–305, 2005) that all K-trivial reals are low. In this paper, we prove that if ${{\bf h'} \geq_T {\bf 0''}}$ , then h (...)
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • Schnorr trivial sets and truth-table reducibility.Johanna N. Y. Franklin & Frank Stephan - 2010 - Journal of Symbolic Logic 75 (2):501-521.
    We give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations allow us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey, Griffiths and LaForte.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  • Hyperimmune-free degrees and Schnorr triviality.Johanna N. Y. Franklin - 2008 - Journal of Symbolic Logic 73 (3):999-1008.
    We investigate the relationship between lowness for Schnorr randomness and Schnorr triviality. We show that a real is low for Schnorr randomness if and only if it is Schnorr trivial and hyperimmune free.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Anti-Complex Sets and Reducibilities with Tiny Use.Johanna N. Y. Franklin, Noam Greenberg, Frank Stephan & Guohua Wu - 2013 - Journal of Symbolic Logic 78 (4):1307-1327.
  • 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 (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Relativizing chaitin's halting probability.Rod Downey, Denis R. Hirschfeldt, Joseph S. Miller & André Nies - 2005 - Journal of Mathematical Logic 5 (02):167-192.
    As a natural example of a 1-random real, Chaitin proposed the halting probability Ω of a universal prefix-free machine. We can relativize this example by considering a universal prefix-free oracle machine U. Let [Formula: see text] be the halting probability of UA; this gives a natural uniform way of producing an A-random real for every A ∈ 2ω. It is this operator which is our primary object of study. We can draw an analogy between the jump operator from computability theory (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   19 citations  
  • On Schnorr and computable randomness, martingales, and machines.Rod Downey, Evan Griffiths & Geoffrey Laforte - 2004 - Mathematical Logic Quarterly 50 (6):613-627.
    We examine the randomness and triviality of reals using notions arising from martingales and prefix-free machines.
    No categories
    Direct download  
     
    Export citation  
     
    Bookmark   13 citations  
  • Promptness Does Not Imply Superlow Cuppability.David Diamondstone - 2009 - Journal of Symbolic Logic 74 (4):1264 - 1272.
    A classical theorem in computability is that every promptly simple set can be cupped in the Turing degrees to some complete set by a low c.e. set. A related question due to A. Nies is whether every promptly simple set can be cupped by a superlow c.e. set, i. e. one whose Turing jump is truth-table reducible to the halting problem θ'. A negative answer to this question is provided by giving an explicit construction of a promptly simple set that (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  • Order-Computable Sets.Denis Hirschfeldt, Russell Miller & Sergei Podzorov - 2007 - Notre Dame Journal of Formal Logic 48 (3):317-347.
    We give a straightforward computable-model-theoretic definition of a property of \Delta^0_2 sets called order-computability. We then prove various results about these sets which suggest that, simple though the definition is, the property defies any easy characterization in pure computability theory. The most striking example is the construction of two computably isomorphic c.e. sets, one of which is order-computable and the other not.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • The Strength of the Rainbow Ramsey Theorem.Barbara F. Csima & Joseph R. Mileti - 2009 - Journal of Symbolic Logic 74 (4):1310 - 1324.
    The Rainbow Ramsey Theorem is essentially an "anti-Ramsey" theorem which states that certain types of colorings must be injective on a large subset (rather than constant on a large subset). Surprisingly, this version follows easily from Ramsey's Theorem, even in the weak system RCA₀ of reverse mathematics. We answer the question of the converse implication for pairs, showing that the Rainbow Ramsey Theorem for pairs is in fact strictly weaker than Ramsey's Theorem for pairs over RCA₀. The separation involves techniques (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  • Extending and interpreting Post’s programme.S. Cooper - 2010 - Annals of Pure and Applied Logic 161 (6):775-788.
    Computability theory concerns information with a causal–typically algorithmic–structure. As such, it provides a schematic analysis of many naturally occurring situations. Emil Post was the first to focus on the close relationship between information, coded as real numbers, and its algorithmic infrastructure. Having characterised the close connection between the quantifier type of a real and the Turing jump operation, he looked for more subtle ways in which information entails a particular causal context. Specifically, he wanted to find simple relations on reals (...)
    Direct download (2 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  
  • 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 (6 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • 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 (6 more)  
     
    Export citation  
     
    Bookmark  
  • Extending and interpreting Post’s programme.S. Barry Cooper - 2010 - Annals of Pure and Applied Logic 161 (6):775-788.
    Computability theory concerns information with a causal–typically algorithmic–structure. As such, it provides a schematic analysis of many naturally occurring situations. Emil Post was the first to focus on the close relationship between information, coded as real numbers, and its algorithmic infrastructure. Having characterised the close connection between the quantifier type of a real and the Turing jump operation, he looked for more subtle ways in which information entails a particular causal context. Specifically, he wanted to find simple relations on reals (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  • Martin–Löf random generalized Poisson processes.Logan Axon - 2018 - Annals of Pure and Applied Logic 169 (4):261-276.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  • Martin-löf randomness in spaces of closed sets.Logan M. Axon - 2015 - Journal of Symbolic Logic 80 (2):359-383.
  • Indeterminism and Undecidability.Klaas Landsman - forthcoming - In Undecidability, Uncomputability, and Unpredictability. Cham: Springer Nature.
    The aim of this paper is to argue that the (alleged) indeterminism of quantum mechanics, claimed by adherents of the Copenhagen interpretation since Born (1926), can be proved from Chaitin's follow-up to Goedel's (first) incompleteness theorem. In comparison, Bell's (1964) theorem as well as the so-called free will theorem-originally due to Heywood and Redhead (1983)-left two loopholes for deterministic hidden variable theories, namely giving up either locality (more precisely: local contextuality, as in Bohmian mechanics) or free choice (i.e. uncorrelated measurement (...)
    Direct download  
     
    Export citation  
     
    Bookmark   1 citation