The strong measure zero sets of reals have been widely studied in the context of set theory of the real line. The notion of strong measure zero is straightforwardly effectivized. A set of reals is said to be of effective strong measure zero if for any computable sequence {εn}n∈N{εn}n∈N of positive rationals, a sequence of intervals InIn of diameter εnεn covers the set. We observe that a set is of effective strong measure zero if and only if it is of (...) measure zero with respect to any outer measure constructed by Monroe's Method from a computable atomless outer premeasure defined on all open balls. This measure-theoretic restatement permits many characterizations of strong measure zero in terms of semimeasures as well as martingales. We show that for closed subsets of Cantor space, effective strong nullness is equivalent to another well-studied notion called diminutiveness , the property of not having a computably perfect subset. Further, we prove that if P is a nonempty effective strong measure zero Π01 set consisting only of noncomputable elements, then some Martin-Löf random reals compute no element in P , and P has an element that computes no autocomplex real. Finally, we construct two different special Π01 sets, one of which is not of effective strong measure zero, but consists only of infinitely-often K-trivial reals, and the other is perfect and of effective strong measure zero, but contains no anti-complex reals. (shrink)

Early work on the frequency theory of probability made extensive use of the notion of randomness, conceived of as a property possessed by disorderly collections of outcomes. Growing out of this work, a rich mathematical literature on algorithmic randomness and Kolmogorov complexity developed through the twentieth century, but largely lost contact with the philosophical literature on physical probability. The present chapter begins with a clarification of the notions of randomness and probability, conceiving of the former as a property of a (...) sequence of outcomes, and the latter as a property of the process generating those outcomes. A discussion follows of the nature and limits of the relationship between the two notions, with largely negative verdicts on the prospects for any reduction of one to the other, although the existence of an apparently random sequence of outcomes is good evidence for the involvement of a genuinely chancy process. (shrink)

The concept of randomness has been unjustly neglected in recent philosophical literature, and when philosophers have thought about it, they have usually acquiesced in views about the concept that are fundamentally flawed. After indicating the ways in which these accounts are flawed, I propose that randomness is to be understood as a special case of the epistemic concept of the unpredictability of a process. This proposal arguably captures the intuitive desiderata for the concept of randomness; at least it should suggest (...) that the commonly accepted accounts cannot be the whole story and more philosophical attention needs to be paid. 1. Randomness in science1.1Random systems1.2Random behaviour1.3Random sampling1.4Caprice, arbitrariness and noise2. Concepts of randomness2.1Von Mises/church/martin-löf randomness2.2KCS-randomness3. Randomness is unpredictability: preliminaries3.1Process and product randomness3.2Randomness is indeterminism?4. Predictability4.1Epistemic constraints on prediction4.2Computational constraints on prediction4.3Pragmatic constraints on prediction4.4Prediction defined5. Unpredictability6. Randomness is unpredictability6.1Clarification of the definition of randomness6.2Randomness and probability6.3Subjectivity and context sensitivity of randomness7. Evaluating the analysis[R]andomness … is going to be a concept which is relative to our body of knowledge, which will somehow reflect what we know and what we don't know. Henry E. Kyburg, Jr ([1974], p. 217)Phenomena that we cannot predict must be judged random. Patrick Suppes ([1984], p. 32). (shrink)

There is a huge chasm between the notion of lawful determination that figures in fundamental physics, and the notion of causal determination that figures in the "folk physics" of everyday objects. In everyday life, we think of the behavior of an ordinary object as being determined by a small set of simple conditions. But in fundamental physics, no such conditions suffice to determine an ordinary object's behavior. What bridges the chasm is that fundamental physical laws make the folk picture of (...) the world approximately true in certain domains. How? In part, by entailing that many objects are approximately isolated from most of their environments. Dynamical laws yield this result only in conjunction with appropriate statistical assumptions about initial conditions. (shrink)

We investigate the initial segment complexity of random reals. Let K denote prefix-free Kolmogorov complexity. A natural measure of the relative randomness of two reals α and β is to compare complexity K and K. It is well-known that a real α is 1-random iff there is a constant c such that for all n, Kn−c. We ask the question, what else can be said about the initial segment complexity of random reals. Thus, we study the fine behaviour of K (...) for random α. Following work of Downey, Hirschfeldt and LaForte, we say that αK β iff there is a constant such that for all n, . We call the equivalence classes under this measure of relative randomness K-degrees. We give proofs that there is a random real α so that lim supn K−K=∞ where Ω is Chaitin's random real. One is based upon work of Solovay, and the other exploits a new idea. Further, based on this new idea, we prove there are uncountably many K-degrees of random reals by proving that μ=0. As a corollary to the proof we can prove there is no largest K-degree. Finally we prove that if n ≠ m then the initial segment complexities of the natural n- and m-random sets and Ω︀) are different. The techniques introduced in this paper have already found a number of other applications. (shrink)

This paper initiates the study of sets in Euclidean spaces ℝn that are defined in terms of the dimensions of their elements. Specifically, given an interval I ⊆ [0, n ], we are interested in the connectivity properties of the set DIMI, consisting of all points in ℝn whose dimensions lie in I, and of its dual DIMIstr, consisting of all points whose strong dimensions lie in I. If I is [0, 1) or.