Geodesic
Solvability of the halting problem for certain classes of Turing machines
Matematičeskie zametki, Tome 13 (1973) no. 6, pp. 899-909 
L. M. Pavlotskaya. Solvability of the halting problem for certain classes of Turing machines. Matematičeskie zametki, Tome 13 (1973) no. 6, pp. 899-909. http://geodesic.mathdoc.fr/item/MZM_1973_13_6_a12/
@article{MZM_1973_13_6_a12,
     author = {L. M. Pavlotskaya},
     title = {Solvability of the halting problem for certain classes of {Turing} machines},
     journal = {Matemati\v{c}eskie zametki},
     pages = {899--909},
     year = {1973},
     volume = {13},
     number = {6},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_1973_13_6_a12/}
}
TY  - JOUR
AU  - L. M. Pavlotskaya
TI  - Solvability of the halting problem for certain classes of Turing machines
JO  - Matematičeskie zametki
PY  - 1973
SP  - 899
EP  - 909
VL  - 13
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/MZM_1973_13_6_a12/
LA  - ru
ID  - MZM_1973_13_6_a12
ER  - 
%0 Journal Article
%A L. M. Pavlotskaya
%T Solvability of the halting problem for certain classes of Turing machines
%J Matematičeskie zametki
%D 1973
%P 899-909
%V 13
%N 6
%U http://geodesic.mathdoc.fr/item/MZM_1973_13_6_a12/
%G ru
%F MZM_1973_13_6_a12

Voir la notice de l'article provenant de la source Math-Net.Ru

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.