Solvability of the halting problem for certain classes of Turing machines

One method of proving that some Turing machine is not universal is to prove that the halting problem is solvable for it. Therefore, to obtain a lower bound on the complexity of a universal machine, it is convenient to have a criterion of solvability of the halting problem. In the present paper, we establish some of these criteria; they are formulated in terms of properties of machine graphs and computations.Translated from Matematicheskie Zametki, Vol. 13, No. 6, pp. 899–909, June, 1973.In conclusion, the author wishes to thank S. V. Yablonskii for discussing this work, and for a number of valuable comments, as well as O. B. Lupanov for suggestions.