Four small universal turing machines

被引：0
|
作者：
Neary, Turlough [1 ]
Woods, Damien [2 ]
机构：
[1] Natl Univ Ireland Maynooth, Dept Comp Sci, TASS, Maynooth, Kildare, Ireland
[2] Univ Coll Cork, Dept Comp Sci, Cork, Ireland
来源：
MACHINES, COMPUTATIONS, AND UNIVERSALITY, PROCEEDINGS | 2007年 / 4664卷
基金：
爱尔兰科学基金会;
关键词：
D O I：
暂无
中图分类号：
TP3 [计算技术、计算机技术];
学科分类号：
0812 ;
摘要：
We present small polynomial time universal Turing machines with state-symbol pairs of (5,5), (6,4), (9,3) and (18,2). These machines simulate our new variant of tag system, the bi-tag system and are the smallest known universal Turing machines with 5, 4, 3 and 2-symbols respectively. Our 5-symbol machine uses the same number of instructions (22) as the smallest known universal Turing machine by Rogozhin.
引用
收藏
页码：242 / +
页数：3
相关论文
共 50 条
  • [1] Four Small Universal Turing Machines
    Neary, Turlough
    Woods, Damien
    FUNDAMENTA INFORMATICAE, 2009, 91 (01) : 123 - 144
  • [2] Small universal turing machines
    Rogozhin, Y
    THEORETICAL COMPUTER SCIENCE, 1996, 168 (02) : 215 - 240
  • [3] Small fast universal Turing machines
    Neary, Turlough
    Woods, Damien
    THEORETICAL COMPUTER SCIENCE, 2006, 362 (1-3) : 171 - 195
  • [4] Small Turing universal signal machines
    Durand-Lose, Jerome
    ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 2009, (01): : 70 - 80
  • [5] Small Weakly Universal Turing Machines
    Neary, Turlough
    Woods, Damien
    FUNDAMENTALS OF COMPUTATION THEORY, PROCEEDINGS, 2009, 5699 : 262 - +
  • [6] The complexity of small universal turing machines
    Woods, Damien
    Neary, Turlough
    COMPUTATION AND LOGIC IN THE REAL WORLD, PROCEEDINGS, 2007, 4497 : 791 - +
  • [7] The Complexity of Small Universal Turing Machines: A Survey
    Neary, Turlough
    Woods, Damien
    SOFSEM 2012: THEORY AND PRACTICE OF COMPUTER SCIENCE, 2012, 7147 : 385 - +
  • [8] SOME SMALL, MULTITAPE UNIVERSAL TURING MACHINES
    HOOPER, PK
    INFORMATION SCIENCES, 1969, 1 (02) : 205 - &
  • [9] The complexity of small universal Turing machines: A survey
    Woods, Damien
    Neary, Turlough
    THEORETICAL COMPUTER SCIENCE, 2009, 410 (4-5) : 443 - 450
  • [10] Small Semi-Weakly Universal Turing Machines
    Woods, Damien
    Neary, Turlough
    FUNDAMENTA INFORMATICAE, 2009, 91 (01) : 179 - 195
12345