Weaker variants of infinite time Turing machines (Q2309496)

The paper is devoted to infinite time Turing machines (for short: ITTM). ITTM are Turing machines that can halt and provide a result after infinitely many steps. They are far more powerful than ordinary Turing machines. They were introduced by \textit{J. D. Hamkins} and \textit{A. Lewis} [J. Symb. Log. 65, No. 2, 567--604 (2000; Zbl 0963.03064)], In the paper under review, models of infinitary computation whose computational power lies strictly between that of Turing machines and ITTMs are investigated. Four types of weak infinite time Turing machines are defined and some results about their computational power are proved. Special attention is paid to so called weak infinite time Turing machines (wITTM). They are defined by replacing in tye definitione of ITTM the lim sup rule with an `eventually constant' rule: at each limit step, the value of each cell isdefined if and only if the content of that cell has stabilized before that limit step and is then equal to this constant value. The author studies different variants of wITTMs adding multiple tapes, heads, or bidimensional tapes. It is shown that some of these models are equivalent to each other concerning their computational strength and that wITTMs decide exactly the arithmetic relations on natural numbers.