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