Output concepts for accelerated Turing machines |
| |
Authors: | Petrus H Potgieter Elemér E Rosinger |
| |
Affiliation: | (1) Department of Decision Sciences, University of South Africa (Unisa), P.O. Box 392, Pretoria, 0003, South Africa;(2) Department of Mathematics and Applied Mathematics, University of Pretoria, Pretoria, 0002, South Africa |
| |
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 computation. 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|