Mathematical Structures in Computer Science

Paper

A note on accelerated Turing machines

CRISTIAN S. CALUDEa1 and LUDWIG STAIGERa2

a1 Department of Computer Science, The University of Auckland, Private Bag 92019, Auckland, New Zealand Email: cristian@cs.auckland.ac.nz

a2 Martin-Luther-Universität Halle-Wittenberg, Institut für Informatik, D - 06099 Halle, Germany Email: staiger@informatik.uni-halle.de

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.

(Received April 22 2009)

(Revised June 10 2010)