Linear-time simulation of multihead Turing machines

DOI10.1016/0890-5401(89)90037-0MaRDI QIDQ1825664zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 1989

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

Full work available at URL https://doi.org/10.1016/0890-5401(89)90037-0

zbMATH Keywords

computational complexitycomputational powerd-dimensional k-head machined-dimensional k-tape machine

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape
• scientific article; zbMATH DE number 2077107
• On the simulation of many storage heads by one
• On heads versus tapes
• scientific article; zbMATH DE number 17549

Cites work

• Boolean Memories
• scientific article; zbMATH DE number 3482367 (Why is no real title available?)
• scientific article; zbMATH DE number 3800926 (Why is no real title available?)
• k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines)
• On heads versus tapes
• On the Computational Complexity of Algorithms
• Real-Time Simulation of Multihead Tape Units
• Two-Tape Simulation of Multitape Turing Machines
• Zwei-Band Simulation von Turingmaschinen. (Two-tape simulation of Turing machines)

Cited in

(7)

• Theory of one-tape linear-time Turing machines
• Matching upper and lower bounds for simulations of several linear tapes on one multidimensional tape
• ``Viral Turing machines, computation from noise and combinatorial hierarchies
• On efficient simulations of multicounter machines
• scientific article; zbMATH DE number 2077107 (Why is no real title available?)
• scientific article; zbMATH DE number 786490 (Why is no real title available?)
• SOFSEM 2004: Theory and Practice of Computer Science

This page was built for publication: Linear-time simulation of multihead Turing machines

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