Small Weakly Universal Turing Machines

被引：0
|
作者：
Neary, Turlough [1 ]
Woods, Damien [2 ]
机构：
[1] Univ Coll Cork, Boole Ctr Res Informat, Cork, Ireland
[2] Univ Seville, Dept Comp Sci & Artificial Intelligence, Serville, Spain
来源：
FUNDAMENTALS OF COMPUTATION THEORY, PROCEEDINGS | 2009年 / 5699卷
基金：
爱尔兰科学基金会;
关键词：
COMPLEXITY; AUTOMATON;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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. Despite their small size these machines are efficient polynomial time simulators of during machines.
引用
收藏
页码：262 / +
页数：3
相关论文
共 50 条
  • [1] Small Semi-Weakly Universal Turing Machines
    Woods, Damien
    Neary, Turlough
    FUNDAMENTA INFORMATICAE, 2009, 91 (01) : 179 - 195
  • [2] Small semi-weakly universal turing machines
    Woods, Damien
    Neary, Turlough
    MACHINES, COMPUTATIONS, AND UNIVERSALITY, PROCEEDINGS, 2007, 4664 : 303 - +
  • [3] Small universal turing machines
    Rogozhin, Y
    THEORETICAL COMPUTER SCIENCE, 1996, 168 (02) : 215 - 240
  • [4] Four small universal turing machines
    Neary, Turlough
    Woods, Damien
    MACHINES, COMPUTATIONS, AND UNIVERSALITY, PROCEEDINGS, 2007, 4664 : 242 - +
  • [5] Small fast universal Turing machines
    Neary, Turlough
    Woods, Damien
    THEORETICAL COMPUTER SCIENCE, 2006, 362 (1-3) : 171 - 195
  • [6] Small Turing universal signal machines
    Durand-Lose, Jerome
    ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 2009, (01): : 70 - 80
  • [7] The complexity of small universal turing machines
    Woods, Damien
    Neary, Turlough
    COMPUTATION AND LOGIC IN THE REAL WORLD, PROCEEDINGS, 2007, 4497 : 791 - +
  • [8] Four Small Universal Turing Machines
    Neary, Turlough
    Woods, Damien
    FUNDAMENTA INFORMATICAE, 2009, 91 (01) : 123 - 144
  • [9] The Complexity of Small Universal Turing Machines: A Survey
    Neary, Turlough
    Woods, Damien
    SOFSEM 2012: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2012, 7147 : 385 - +
  • [10] SOME SMALL, MULTITAPE UNIVERSAL TURING MACHINES
    HOOPER, PK
    INFORMATION SCIENCES, 1969, 1 (02) : 205 - &
12345