On the time complexity of 2-tag systems and small universal Turing machines
On the time complexity of 2-tag systems and small universal Turing machines
复制标题
关于2标签系统和小型通用图灵机的时间复杂度
DOI：
10.1109/focs.2006.58
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Turlough Neary
中科院分区：
文献类型：
--
作者：
D. Woods;Turlough Neary
我们表明，2标签系统有效地模拟图灵机。作为推论，我们发现Rogozhin，Minsky和其他人的小型通用图灵机在多项式时间内模拟图灵机。这是对先前已知的模拟时间开销的指数改进，并且改进了小型通用图灵机领域中的四十年前的结果
We show that 2-tag systems efficiently simulate Turing machines. As a corollary we find that the small universal Turing machines of Rogozhin, Minsky and others simulate Turing machines in polynomial time. This is an exponential improvement on the previously known simulation time overhead and improves a forty year old result in the area of small universal Turing machines