UC Irvine

The general aim of this thesis is to explore applications of transfinite computation within the philosophy of mathematics|particularly the foundations and philosophy of set theory and to contribute to the young but rapidly growing literature on the technical capabilities and limits of transfinite computation. The material is divided into two main parts. The first concerns transfinite recursion, an essential component of the practice of set theory. Here we seek intrinsically justified reasons for believing in transfinite recursion and the notions of higher computation that surround it. In doing so, we consider several kinds of recursion principle and prove results concerning their relation to one another. Next, philosophical motivations are considered for these formal principles, coming from the idea that computational notions lie at the core of our conception of set. This is significant because, while the iterative conception of set has been widely recognized as insufficient to establish Replacement and recursion, its supplementation by considerations pertaining to algorithms suggests a new and philosophically well-motivated reason to believe in such principles.

The second part addresses technical questions on the mathematical capabilities and limits of a family of models of transfinite computation. These models resemble the infinite-time Turing machine (ITTM) model of Hamkins and Lewis, except with α-length tape (for some ordinal α < ω). Let T_{α<\sub> denote the machine model of tape length α (so Tω<\sub> is equivalent to the ITTM model). Define that Tα<\sub> is computationally stronger<\italic> than Tβ<\sub> (abbreviated Tα<\sub> > Tβ<\sub> ) precisely when Tα<\sub> can compute all Tβ<\sub>-computable functions on binary input strings of size min(α,β), plus more. The following results are found: (1) Tω1<\sub> > Tω<\sub>. (2) There are countable ordinals α such that Tα<\sub> > Tω<\sub>, the smallest of which is the supremum of ordinals clockable by Tω<\sub>. In fact, there is a hierarchy of countable Tα<\sub>s of increasing strength corresponding to the transfinite (weak) Turing-jump operator. (3) There is a countable ordinal μ such that neither Tμ<\sub> ≥ Tω1<\sub> nor Tμ<\sub> ≤ Tω1<\sub> --- that is, the models Tμ<\sub> and Tω1<\sub> are computation-strength incommensurable (and the same holds if countable μ' > μ replaces μ). A similar fact holds for any larger uncountable device replacing Tω1<\sub>. (4) Further observations are made about}

countable T_{α<\sub>s, including the existence of incommensurabilities between them.}