Simulations among multidimensional Turing machines

DOI10.1016/0304-3975(89)90081-9zbMath0486.68038OpenAlexW2074159544MaRDI QIDQ1165001

Michael C. Loui

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90081-9

zbMATH Keywords

deterministic multihead Turing machinedynamic embeddings among arrays with local access

Mathematics Subject Classification ID

Related Items

Speedup of determinism by alternation for multidimensional Turing machines, Optimal dynamic embedding of X-trees into arrays, The complexity of on-line simulations between multidimensional turing machines and random access machines, A fast implementation of a multidimensional storage into a tree storage, A note on almost-everywhere-complex sets and separating deterministic- time-complexity classes, Minimizing access pointers into trees and arrays, On the worst case performance of buddy systems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Data encodings and their costs
• An information-theoretic approach to time bounds for on-line computation
• Zwei-Band Simulation von Turingmaschinen. (Two-tape simulation of Turing machines)
• New Real-Time Simulations of Multihead Tape Units
• Storage Modification Machines
• Preserving Proximity in Arrays
• Space and Time Hierarchies for Classes of Control Structures and Data Structures
• Bounds on the costs of data encodings
• Relations Among Complexity Measures
• On the Computational Complexity of Algorithms
• Boolean Memories