Time complexity of multidimensional Turing machines

DOI10.1007/BF01629436zbMath0493.03015MaRDI QIDQ1168311

Dima Yu. Grigoriev

Publication date: 1982

Published in: Journal of Soviet Mathematics (Search for Journal in Brave)

zbMATH Keywords

random access machinesnondeterministic Turing machinerecognition of predicatessimulating multidimensional multi-head Turing machinestime-bound

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Turing machines and related notions (03D10)

Cites Work

• Unnamed Item
• Unnamed Item
• Zwei-Band Simulation von Turingmaschinen. (Two-tape simulation of Turing machines)
• Tape bounds for time-bounded Turing machines
• On Time Versus Space
• On-Line Turing Machine Computations

This page was built for publication: Time complexity of multidimensional Turing machines