Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time

DOI10.1016/0890-5401(92)90026-CzbMath0753.68040MaRDI QIDQ1193594

John Michael Robson

Publication date: 27 September 1992

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

zbMATH Keywords

Turing machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

Linear speed-up does not hold on Turing machines with tree storages

Cites Work

• Unnamed Item
• Unnamed Item
• Time bounded random access machines
• Fast probabilistic RAM simulation of single tape turing machine computations

This page was built for publication: Deterministic simulation of a single tape turing machine by a random access machine in sub-linear time