Linear-time simulation of multihead Turing machines

DOI10.1016/0890-5401(89)90037-0zbMath0684.68069OpenAlexW2012446541MaRDI QIDQ1825664

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)

Related Items (1)

``Viral Turing machines, computation from noise and combinatorial hierarchies

Cites Work

• Unnamed Item
• Unnamed Item
• On heads versus tapes
• k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines)
• Zwei-Band Simulation von Turingmaschinen. (Two-tape simulation of Turing machines)
• On the Computational Complexity of Algorithms
• Boolean Memories
• Two-Tape Simulation of Multitape Turing Machines
• Real-Time Simulation of Multihead Tape Units

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