Turing machines with access to history

DOI10.1016/0890-5401(90)90008-6zbMATH Open0715.68023OpenAlexW2023618654MaRDI QIDQ751802FDOQ751802

Authors: Bogdan S. Chlebus 

Publication date: 1990

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(90)90008-6

Recommendations

• On the Computational Power of Querying the History
• scientific article; zbMATH DE number 3850476
• scientific article; zbMATH DE number 3984575
• On reversal bounded alternating Turing machines
• A hierarchy of fast reversible Turing machines

zbMATH Keywords

remembering Turing machines

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Title not available (Why is that?)
• Alternation
• The complexity of two-player games of incomplete information
• GO Is Polynomial-Space Hard
• Domino-tiling games
• Title not available (Why is that?)
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• N by N Checkers is Exptime Complete
• Title not available (Why is that?)
• Solitaire automata
• Writing pushdown acceptors
• Alternation with restrictions on looping
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

This page was built for publication: Turing machines with access to history

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q751802)