Four Small Universal Turing Machines
From MaRDI portal
Publication:5902079
DOI10.3233/FI-2009-0036zbMath1191.68307MaRDI QIDQ5902079
Publication date: 23 June 2009
Published in: Fundamenta Informaticae (Search for Journal in Brave)
computational complexity; polynomial time; 2-tag system; small universal Turing machine; Post system; bi-tag systems
03D10: Turing machines and related notions
Related Items
Maurice Margenstern’s Contributions to the Field of Small Universal Turing Machines, Verifiable capacity-bound functions: a new primitive from Kolmogorov complexity. (Revisiting space-based security in the adaptive setting), Abstract geometrical computation. IV: Small Turing universal signal machines, On the complex behavior of simple tag systems -- an experimental approach, An automaton group with undecidable order and Engel problems, Inclusion problems for patterns with a bounded number of variables, The Complexity of Small Universal Turing Machines: A Survey, Small Universal Devices