Infinite time computations and infinite algorithms

Abstract

In this paper we investigate infinite time Turing machines as defined by Hamkins and Lewis in [1]. We extend the result in [2] showing that a larger set of clockable ordinals are 1-tape clockable. Furthermore, a new notion of infinite time Turing machine, in which the set of states may be infinite, is compared with the original notion. We show that the strength of such infinite state infinite time machines correspond to the strength of infinite time Turing machines equipped with real-oracles.