X-machines and the halting problem: Building a super-turing machine
- 1 March 1990
- journal article
- Published by Association for Computing Machinery (ACM) in Formal Aspects of Computing
- Vol. 2 (1) , 331-341
- https://doi.org/10.1007/bf01888233
Abstract
We describe a novel machine model of computation, and prove that this model is capable of performing calculations beyond the capability of the standard Turing machine model. In particular, we demonstrate the ability of our model to solve the Halting problem for Turing machines. We discuss the issues involved in implementing the model as a physical device, and offer some tentative suggestions.Keywords
This publication has 4 references indexed in Scilit:
- The Emperor's New MindPublished by Oxford University Press (OUP) ,1989
- X-machines as a basis for dynamic system specificationSoftware Engineering Journal, 1988
- ComputabilityPublished by Cambridge University Press (CUP) ,1980
- Lebesgue Integration and MeasurePublished by Cambridge University Press (CUP) ,1973