Four Small Universal Turing Machines

DOI10.3233/FI-2009-0036zbMath1191.68307MaRDI QIDQ5902079

Turlough Neary, Damien Woods

Publication date: 23 June 2009

Published in: Fundamenta Informaticae (Search for Journal in Brave)

zbMATH Keywords

computational complexitypolynomial time2-tag systemsmall universal Turing machinePost systembi-tag systems

Mathematics Subject Classification ID

Turing machines and related notions (03D10)

Related Items (8)

The Complexity of Small Universal Turing Machines: A Survey ⋮ Small Universal Devices ⋮ Abstract geometrical computation. IV: Small Turing universal signal machines ⋮ On the complex behavior of simple tag systems -- an experimental approach ⋮ Inclusion problems for patterns with a bounded number of variables ⋮ Verifiable capacity-bound functions: a new primitive from Kolmogorov complexity. (Revisiting space-based security in the adaptive setting) ⋮ An automaton group with undecidable order and Engel problems ⋮ Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines

This page was built for publication: Four Small Universal Turing Machines