Article contents
A note on accelerated Turing machines
Published online by Cambridge University Press: 08 November 2010
Abstract
In this paper we prove that any Turing machine that uses only a finite computational space for every input cannot solve an uncomputable problem even when it runs in accelerated mode. We also propose two ways to define the language accepted by an accelerated Turing machine. Accordingly, the classes of languages accepted by accelerated Turing machines are the closure under Boolean operations of the sets Σ1 and Σ2.
- Type
- Paper
- Information
- Mathematical Structures in Computer Science , Volume 20 , Special Issue 6: Quantum Algorithms , December 2010 , pp. 1011 - 1017
- Copyright
- Copyright © Cambridge University Press 2010
References
- 7
- Cited by