Small Weakly Universal Turing Machines

DOI10.1007/978-3-642-03409-1_24MaRDI QIDQ3183617zbMATH OpenOpenAlexFDO

Authors Turlough Neary, Damien Woods

Publication date 20 October 2009

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0707.4489

Mathematics Subject Classification ID

Abstract: We give small universal Turing machines with state-symbol pairs of (6, 2), (3, 3) and (2, 4). These machines are weakly universal, which means that they have an infinitely repeated word to the left of their input and another to the right. They simulate Rule 110 and are currently the smallest known weakly universal Turing machines.

Recommendations

• Small Semi-Weakly Universal Turing Machines
• Small Semi-weakly Universal Turing Machines
• The Complexity of Small Universal Turing Machines
• The Complexity of Small Universal Turing Machines: A Survey
• The complexity of small universal Turing machines: A survey

Cited in

(23)

• The complexity of small universal Turing machines: A survey
• Some small self-describing Turing machines
• Small fast universal Turing machines
• Wang's B machines are efficiently universal, as is Hasenjaeger's small universal electromechanical toy
• Turing patterns with Turing machines: emergence and low-level structure formation
• Yurii Rogozhin's contributions to the field of small universal Turing machines
• The Complexity of Small Universal Turing Machines: A Survey
• Universality in infinite Petri nets
• Universal Sleptsov net
• Small Semi-weakly Universal Turing Machines
• Small Semi-Weakly Universal Turing Machines
• MINSKY'S SMALL UNIVERSAL TURING MACHINE
• scientific article; zbMATH DE number 1992427 (Why is no real title available?)
• Three small universal spiking neural P systems
• A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory
• The Complexity of Small Universal Turing Machines
• A Note on Computation MTs with Time in Instructions or with Tapes of Fixed Length
• Four Small Universal Turing Machines
• Four Small Universal Turing Machines
• Abstract geometrical computation. IV: Small Turing universal signal machines
• A simple P-complete problem and its language-theoretic representations
• On the complex behavior of simple tag systems -- an experimental approach
• Linear Bounds on the Size of Conformations in Greedy Deterministic Oritatami

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3183617)