Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  Print this page

Regular Talk:
Infinite time register machines

Speaker: Peter Koepke
Slot: Sat, 15:10-15:30, Faraday D (col. 3)

Abstract

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 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by www.free-counters.net