Mathematical and Philosophical Perspectives on Algorithmic Randomness

Doctoral Dissertation


The mathematics portion of this dissertation is a study of the various interactions between definitions of algorithmic randomness, Turing functionals, and non-uniform probability measures on Cantor space. In Chapter 3, we study the connection between Turing functionals and a number of different definitions of randomness, culminating in a number of characterizations of these definitions of randomness in terms of a priori complexity, a notion of initial segment complexity given in terms of Turing functionals. In Chapter 4, we investigate possible generalizations of Demuth’s Theorem, an important theorem in algorithmic randomness concerning the behavior of random sequences under truth-table reducibility. One technique developed in this chapter, that of inducing a probability measure by means of a special type of truth-table functional that we call a tally functional, proves to be very useful. We use this technique to study randomness with respect to trivial computable measures in both Chapters 5 and 6.

In the philosophy portion of this dissertation, we consider the problem of producing a correct definition of randomness. Some have claim that one definition of randomness in particular, Martin-Lf randomness, captures the so-called intuitive conception of randomness, a claim known as the Martin-Lf-Chaitin Thesis. Prior to evaluating the Martin-Lf-Chaitin Thesis and related randomness-theoretic theses, in Chapters 8 and 9 we discuss two roles of definitions of randomness, both of which motivated much early work in the development of algorithmic randomness: the resolutory role of randomness, which is successfully filled by a definition of randomness that allows for the solution of problems in a specific theory of probability, and the exemplary role of randomness, which is successfully filled by a definition of randomness that counts as random certain sequences that exemplify the properties typically held by sequences chosen at random. In Chapter 10, we lay out the status of the Martin-Lf-Chaitin Thesis, discussing the evidence that has been offered in support of it, as well as the arguments that have been raised against it. In Chapter 11, we argue that the advocate of a claim like the Martin-Lf-Chaitin Thesis faces what we call the Justificatory Challenge: she must present a precise account of the so-called intuitive conception of randomness, so as to justify the claim that her preferred definition of randomness is the correct one and block the claim of correctness made on behalf of alternative definitions of randomness. Lastly, in Chapter 12, we present two further roles for definitions of randomness to play, which we call the calibrative role of randomness and the limitative role of randomness, which can be successfully filled by multiple definitions of randomness. Definitions filling the calibrative role allow us to calibrate the level of randomness necessary and sufficient for certain “almost-everywhere" results in classical mathematics to hold, while definitions filling the limitative role illuminate a phenomenon known as the indefinite contractibility of the notion of randomness. Moreover, we argue that in light of the fact that many definitions can successfully fill these two roles, we should accept what we call the No-Thesis Thesis: there is no definition of randomness that (i) yields a well-defined, definite collection of random sequences and (ii) captures everything that mathematicians have taken to be significant about the concept of randomness.


Attribute NameValues
  • etd-04202012-160648

Author Christopher Porter
Advisor Peter Cholak
Contributor Peter Cholak, Committee Co-Chair
Contributor Michael Detlefsen, Committee Co-Chair
Contributor Curtis Franks, Committee Co-Chair
Contributor Laurent Bienvenu, Committee Member
Contributor Julia Knight, Committee Member
Contributor Timothy McCarthy, Committee Member
Degree Level Doctoral Dissertation
Degree Discipline Philosophy
Degree Name Doctor of Philosophy
Defense Date
  • 2012-04-11

Submission Date 2012-04-20
  • United States of America

  • algorithmic randomness

  • philosophy of mathematics

  • University of Notre Dame

  • English

Record Visibility Public
Content License
  • All rights reserved

Departments and Units

Digital Object Identifier


This DOI is the best way to cite this doctoral dissertation.


Please Note: You may encounter a delay before a download begins. Large or infrequently accessed files can take several minutes to retrieve from our archival storage system.