Infinite Time Turing Machines with Finite Space

Date

2025-8-04

Author

Sadeghi Aval, Yekta

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

3298
views

0
downloads

Cite This

Infinite time Turing machines (ITTMs), introduced by Hamkins and Lewis, extend classical computation into transfinite ordinal time. In this thesis, we study ITTMs with space restrictions. After presenting fundamental results about standard ITTMs and some of its variants, we investigate the halting behavior of ITTMs that use finite computational space. In particular, we revisit the result of Defrain, Durand and Lafitte that the halting time of such an ITTM cannot exceed ω^ω on each input, with a more detailed analysis and slightly different proofs. We also construct an ITTM that uses finite computational space whose overall halting time is ω^ω. Our results demonstrate how the space restriction on each input affects the halting time.

Subject Keywords

Infinite time Turing machines, Transfinite ordinals, Finite space, Halting time, Clockable ordinals

URI

https://hdl.handle.net/11511/115476

Collections

Graduate School of Natural and Applied Sciences, Thesis