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 complexitypolynomial time2-tag systemsmall universal Turing machinePost systembi-tag systems
Related Items
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