Capabilities and Limitations of Infinite-Time Computation

The relatively new field of infinitary computability strives to characterize thecapabilities and limitations of infinite-time computation; that is, computations ofpotentially transfinite length. Throughout our work, we focus on the prototypicalmodel of infinitary computation: Hamkins and Lewis\u27 infinite-time Turing machine(ITTM), which generalizes the classical Turing machine model in a naturalway.This dissertation adopts a novel approach to this study: whereas most of theliterature, starting with Hamkins and Lewis\u27 debut of the ITTM model, pursuesset-theoretic questions using a set-theoretic approach, we employ arguments thatare truly computational in character. Indeed, we fully utilize analogues of classicalresults from finitary computability, such as the s-m-n Theorem and existence ofuniversal machines, and for the most part, judiciously restrict our attention to theclassical setting of computations over the natural numbers.In Chapter 2 of this dissertation, we state, and derive, as necessary, the aforementionedanalogues of the classical results, as well as some useful constructs for ITTM programming. With this due paid, the subsequent work in Chapters 3 and 4 requires little in the way of programming, and that programming which is required in Chapter 5 is dramatically streamlined. In Chapter 3, we formulate two analogues of one of Rado\u27s busy beaver functions from classical computability, and show, in analogy with Rado\u27s results, that they grow faster than a wide class of infinite-time computable functions. Chapter 4 is tasked with developing a system of ordinal notations via a natural approach involving infinite-time computation, as well as an associated fast-growing hierarchy of functions over the natural numbers. We then demonstrate that the busy beaver functions from Chapter 3 grow faster than the functions which appear in a significant portion of this hierarchy. Finally, we debut, in Chapter 5, two enhancements of the ITTM model whichcan self-modify certain aspects of their underlying software and hardware mid-computation, and show the somewhat surprising fact that, under some reasonableassumptions, these new models of infinitary computation compute precisely thesame functions as the original ITTM model