Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and Normal Form theorems

Research output: Contribution to journalArticle (Academic Journal)peer-review

18 Citations (Scopus)

Abstract

We give an acount of the basic determinants of the courses of computation of the Infinite Time Turing Machine model of Hamkins and Kidder, a model of computation which allows for transfinitely many steps of computation, and therefore may accept and output infinite strings of bits. We provide, inter alia, a Normal form Theorem, and a characterisation of which ordinals start gaps in halting times of such machines.
Translated title of the contributionCharacteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and Normal Form theorems
Original languageEnglish
Pages (from-to)426 - 442
Number of pages17
JournalTheoretical Computer Science
Volume410
Issue number4-5
DOIs
Publication statusPublished - 17 Feb 2009

Bibliographical note

Publisher: Springer

Fingerprint Dive into the research topics of 'Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and Normal Form theorems'. Together they form a unique fingerprint.

Cite this