Open Access Te Herenga Waka-Victoria University of Wellington
Browse

Topics in Algorithmic Randomness and Computability Theory

Download (767.2 kB)
Version 2 2023-09-26, 23:55
Version 1 2021-11-15, 17:19
thesis
posted on 2023-09-26, 23:55 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.

History

Copyright Date

2016-01-01

Date of Award

2016-01-01

Publisher

Te Herenga Waka—Victoria University of Wellington

Rights License

CC BY-NC-ND 4.0

Degree Discipline

Mathematics

Degree Grantor

Te Herenga Waka—Victoria University of Wellington

Degree Level

Doctoral

Degree Name

Doctor of Philosophy

ANZSRC Type Of Activity code

1 PURE BASIC RESEARCH

Victoria University of Wellington Item Type

Awarded Doctoral Thesis

Language

en_NZ

Victoria University of Wellington School

School of Mathematics, Statistics and Operations Research

Advisors

Downey, Rod; Greenberg, Noam