Publication
SWAT 1968
Conference paper

Limited random access turing machines

View publication

Abstract

The model of an online multitape Turing machine is generalized by adding a bounded number of repositioning operations to the shift repertoire. It is proved that any such limited random access Turing machine can be effectively replaced by an equivalent conventional Turing machine which operates in the same time. This result yields simplified proofs and extensions of several results in the literature.

Date

Publication

SWAT 1968

Authors

Topics

Share