The uniform halting problem for generalized one-state turing machines

Abstract

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.