Turing Machines Connected to the Undecidability of the Halting Problem

L. M. Pavlotskaya


Abstract: 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.

UDC: 510.53+512.54.05

Received: 06.12.2000

DOI: 10.4213/mzm381

 English version: Mathematical Notes, 2002, 71:5, 667–675

Bibliographic databases:

• 
• 
• 
•