Towards a Precise Characterization of the Complexity of Universal and Nonuniversal Turing Machines

DOI10.1137/0208041zbMath0426.68024OpenAlexW2052389354MaRDI QIDQ3862403

Lutz Priese

Publication date: 1979

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0208041

zbMATH Keywords

universal Turing machinetwo-dimensional tapenetworks of abstract automataregister-machines

Mathematics Subject Classification ID

Turing machines and related notions (03D10)

Related Items (7)

The Complexity of Small Universal Turing Machines: A Survey ⋮ Small universal Turing machines ⋮ Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy ⋮ The complexity of small universal Turing machines: A survey ⋮ Frontier between decidability and undecidability: A survey ⋮ Automata and concurrency ⋮ Computation theoretic aspects of cellular automata

This page was built for publication: Towards a Precise Characterization of the Complexity of Universal and Nonuniversal Turing Machines