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 contribution||Characteristics of discrete transfinite time Turing machine models: Halting times, stabilization times, and Normal Form theorems|
|Pages (from-to)||426 - 442|
|Number of pages||17|
|Journal||Theoretical Computer Science|
|Publication status||Published - 17 Feb 2009|