Turing machines with access to history

Research output: Contribution to journalArticlepeer-review


We study remembering Turing machines, that is Turing machines with the capability to access freely the history of their computations. These devices can detect in one step via the oracle mechanism whether the storage tapes have exactly the same contents at the moment of inquiry as at some past moment in the computation. The s(n)-space-bounded remembering Turing machines are shown to be able to recognize exactly the languages in the time-complexity class determined by bounds exponential in s(n). This is proved for deterministic, non-deterministic, and alternating Turing machines.

Original languageEnglish (US)
Pages (from-to)133-143
Number of pages11
JournalInformation and Computation
Issue number2
StatePublished - Dec 1990
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Turing machines with access to history'. Together they form a unique fingerprint.

Cite this