Turing machines associated with the undecidability property of the halting problem (Q1810121)

The definition of a connected Turing machine is given as follows: a machine is called connected if the halting problem for this machine is undecidable and by deleting even a single instruction from its program we get a machine with decidable halting problem. The paper is devoted to an analysis of general properties of such machines. The author gives some theorems and deduces their simplest corollaries. She points out some subsets of all initial configurations which are not recursively enumerable for connected machines. The relation between the number of instructions and states of a connected machine is also established. The theorem that any Turing machine with four instructions is not connected is proved.