Logical Approaches to Computational Barriers

Infinite time register machines

Speaker:
| Peter Koepke |

Slot: |
Array, 15:10-15:30, col. 3 |

Infinite time register machines(ITRM's) are register machines which act on natural numbers and which may run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands, at limits the register contents are defined as liminf's of the previous register contents. We prove that a real number is computable by an ITRM iff it is hyperarithmetic.

websites: Arnold Beckmann | 2006-04-19 |