Abstract:
The accelerated Turing machine (ATM) is the work-horse of hypercomputation. In certain cases,
a machine having run through a countably infinite number of steps is supposed to have decided some
interesting question such as the Twin Prime conjecture. One is, however, careful to avoid unnecessary
discussion of either the possible actual use by such a machine of an infinite amount of space, or the
difficulty (even if only a finite amount of space is used) of defining an outcome for machines acting like
Thomson's lamp. It is the authors' impression that insufficient attention has been paid to introducing a
clearly defined counterpart for ATMs of the halting/non-halting dichotomy for classical Turing compu-
tation. This paper tackles the problem of defining the output, or final message, of a machine which has
run for a countably infinite number of steps. Non-standard integers appear quite useful in this regard
and we describe several models of computation using filters.
