О машинах Тьюринга, связных относительно свойства неразрешимости проблемы остановки

Хорошо известна задача поиска машины Тьюринга с неразрешимой проблемой остановки, программа которой содержит минимальное число инструкций. Очевидно, для такой машины выполняется следующее условие: если из ее программы удалить хотя бы только одну инструкцию, получим машину с разрешимой проблемой остановки. В настоящей работе машины Тьюринга с неразрешимой проблемой остановки, обладающие вышесформулированным свойством, названы связными. В работе получены некоторые общие свойства таких машин и простейшие следствия из них, относящиеся к минимальной машине с неразрешимой проблемой остановки.
Библиография: 2 названия.