thesis_access.pdf (767.2 kB)
Download file

Topics in Algorithmic Randomness and Computability Theory

Download (767.2 kB)
posted on 2021-11-15, 17:19 authored by McInerney, Michael

This thesis establishes results in several different areas of computability theory.  The first chapter is concerned with algorithmic randomness. A well-known approach to the definition of a random infinite binary sequence is via effective betting strategies. A betting strategy is called integer-valued if it can bet only in integer amounts. We consider integer-valued random sets, which are infinite binary sequences such that no effective integer-valued betting strategy wins arbitrarily much money betting on the bits of the sequence. This is a notion that is much weaker than those normally considered in algorithmic randomness. It is sufficiently weak to allow interesting interactions with topics from classical computability theory, such as genericity and the computably enumerable degrees. We investigate the computational power of the integer-valued random sets in terms of standard notions from computability theory.  In the second chapter we extend the technique of forcing with bushy trees. We use this to construct an increasing ѡ-sequence 〈an〉 of Turing degrees which forms an initial segment of the Turing degrees, and such that each an₊₁ is diagonally noncomputable relative to an. This shows that the DNR₀ principle of reverse mathematics does not imply the existence of Turing incomparable degrees.   In the final chapter, we introduce a new notion of genericity which we call ѡ-change genericity. This lies in between the well-studied notions of 1- and 2-genericity. We give several results about the computational power required to compute these generics, as well as other results which compare and contrast their behaviour with that of 1-generics.


Copyright Date


Date of Award



Te Herenga Waka—Victoria University of Wellington

Rights License

Author Retains Copyright

Degree Discipline


Degree Grantor

Te Herenga Waka—Victoria University of Wellington

Degree Level


Degree Name

Doctor of Philosophy

ANZSRC Type Of Activity code


Victoria University of Wellington Item Type

Awarded Doctoral Thesis



Victoria University of Wellington School

School of Mathematics, Statistics and Operations Research


Downey, Rod; Greenberg, Noam