UNIFORM HALTING PROBLEM FOR GENERALIZED ONE-STATE TURING MACHINES

被引：2

作者：

HERMAN, GT

机构：

[1] IBM (U.K.) Ltd., Education Centre, Greenford, Middlesex England

来源：

INFORMATION AND CONTROL | 1969年 / 15卷 / 04期

关键词：

D O I：

10.1016/S0019-9958(69)90472-0

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

It is shown that the uniform halting problem for one-state Turing machines is solvable. It remains solvable for various generalizations like one-state Turing machines with two-dimensional tape and jumping reading head. Other generalizations, for example, one-state Turing machines with two tapes, have an unsolvable uniform halting problem. The history of the problem is summarized. © 1969 Academic Press, Inc.

引用

页码：353 / &

共 9 条

[1] SOLVABILITY OF HALTING PROBLEM FOR 2-STATE POST MACHINES [J].