Geodesic
Turing Machines Connected to the Undecidability of the Halting Problem
Matematičeskie zametki, Tome 71 (2002) no. 5, pp. 732-741 
L. M. Pavlotskaya. Turing Machines Connected to the Undecidability of the Halting Problem. Matematičeskie zametki, Tome 71 (2002) no. 5, pp. 732-741. http://geodesic.mathdoc.fr/item/MZM_2002_71_5_a8/
@article{MZM_2002_71_5_a8,
     author = {L. M. Pavlotskaya},
     title = {Turing {Machines} {Connected} to the {Undecidability} of the {Halting} {Problem}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {732--741},
     year = {2002},
     volume = {71},
     number = {5},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2002_71_5_a8/}
}
TY  - JOUR
AU  - L. M. Pavlotskaya
TI  - Turing Machines Connected to the Undecidability of the Halting Problem
JO  - Matematičeskie zametki
PY  - 2002
SP  - 732
EP  - 741
VL  - 71
IS  - 5
UR  - http://geodesic.mathdoc.fr/item/MZM_2002_71_5_a8/
LA  - ru
ID  - MZM_2002_71_5_a8
ER  - 
%0 Journal Article
%A L. M. Pavlotskaya
%T Turing Machines Connected to the Undecidability of the Halting Problem
%J Matematičeskie zametki
%D 2002
%P 732-741
%V 71
%N 5
%U http://geodesic.mathdoc.fr/item/MZM_2002_71_5_a8/
%G ru
%F MZM_2002_71_5_a8

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

The problem of finding a Turing machine with undecidable halting problem whose program contains the smallest number of instructions is well known. Obviously, such a machine must satisfy the following condition: by deleting even a single instruction from its program, we get a machine with decidable halting problem. In this paper, Turing machines with undecidable halting problem satisfying this condition are called connected. We obtain a number of general properties of such machines and deduce their simplest corollaries concerning the minimal machine with undecidable halting problem.

[1] Maltsev A. I., Algoritmy i rekursivnye funktsii, Nauka, M., 1965

[2] Pavlotskaya L. M., “Razreshimost problemy ostanovki dlya nekotorykh klassov mashin Tyuringa”, Matem. zametki, 13:6 (1973), 899–909 | MR | Zbl