Infinite Time Computation: Strong and Weak Infinite Time Turing Machines

Master's Thesis

Abstract

Hamkins and Lewis have used infinite time Turing machines to extend the operations of Turing machines to infinite ordinal time. This project investigates some applications of these machines to basic operations and relations over the reals. It also investigates variants of these machines with extra-tapes or extra read-write heads. Then, this project investigates strictly weaker variants of these machines, which are obtained by allowing the content in each cell to change only finitely often. It is shown that these weaker machines can already compute basic operations and relations over the reals. Finally, the computational power of these machines is further investigated.

Attributes

Attribute NameValues
Author Matteo Bianchetti
Contributor Gregory Igusa, Committee Member
Contributor Peter Cholak, Committee Member
Contributor Julia F. Knight, Research Director
Contributor Michael Detlefsen, Research Director
Degree Level Master's Thesis
Degree Discipline Mathematics
Degree Name MSIM
Defense Date
  • 2017-03-28

Submission Date 2017-03-30
Subject
  • Infinite time computability, Infinite time Turing machines, Transfinite computation, Supertask, Hamkins, Arithmetic hierarchy

Language
  • English

Record Visibility and Access Public
Content License
  • All rights reserved

Departments and Units

Files

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.