[bibtex key=HamkinsLewis2000:InfiniteTimeTM]
This is the seminal paper introducing infinite time Turing machines.
We extend in a natural way the operation of Turing machines to infinite ordinal time, and investigate the resulting supertask theory of computability and decidability on the reals. The resulting computability theory leads to a notion of computation on the reals and concepts of decidability and semi-decidability for sets of reals as well as individual reals. Every $\Pi^1_1$ set, for example, is decidable by such machines, and the semi-decidable sets form a portion of the $\Delta^1_2$ sets. Our oracle concept leads to a notion of relative computability for reals and sets of reals and a rich degree structure, stratified by two natural jump operators.
It seems that infinite time Turing machines are fully deterministic except at the limit stages when cells on the tape are updated to the lim sup of a countable infinity of values that occurred in the cells at non-limit stages. What kind of hardware would we have to imagine added to an ordinary Turing machine to complete the analysis that determines this lim sup for each cell? In other words, how could a machine be built to discover whether the series of cell contents converges to 1 or oscillates continually between 0 and 1?
The limit cell values are deterministic in the sense that the value at the limit is logically determined by earlier values, and it couldn’t be a different value (contrast with non-deterministic computation in finite time, where there is a sense in which the next step of computation is not logically determined by the previous states, since there are multiple paths of computation that all accord with the computational rules). As for the physical implementation, this is an issue for the physicists. I imagine some kind of biased magnetic cell memory, which will show a positive value at a limit if it was unboundedly often positive going in to the limit. Ultimately, of course, what I am interested in is the purely mathematical theory of the resulting class of functions, and so the issue of physical implementation doesn’t actually matter.