Математическая логика и теория алгоритмов

Машина останавливается, если она находится в некотором внутреннем состоянии qj, читающая головка обозревает какой-то сим­ вол 5^, а среди команд машины нет команды, начинающейся с qjSk- Если на ленте имеется какое-нибудь слово Р (в частности, пустое слово), читающая головка помещена на квадрат с первой левой буквой слова Р и машина приведена во внутреннее состояние qo, то машина начинает оперировать на ленте: ее головка стирает и пишет символы и перемещается из одного квадрата в другой (соседний). Если при этом машина когда-нибудь останавливается, то находящееся в момент остановки слово на ленте считается результатом применения машины Т к данному слову Р. Если процесс переработки машиной Т слова Р бесконечен, то говорят, что машина Т н е применима к слову Р. § 8. Задание машины Тьюринга Машина Тьюринга Т считается заданной, если задано непустое конечное мнолсество упорядоченных четверок символов (команд), удовлетворяющих условиям; а) каждая команда (четверка символов) принадлежит к одному из трех типов команд, приведенных в § 7; б) никакие две команды одной машины не имеют совпадающие первые два символа; в) среди команд любой машины всегда есть хотя бы одна команда, начинающаяся с q^. Множество всех символов типа S^, входящих в команды маши­ ны, называется алфавитом заданной машины, а входящие в эти коман­ ды символы q, называются внутренними состояниями заданной ма­ шины Т. Считаем, что в исходном (начальном) состоянии машина обла­ дает внутренним состоянием q^. Для преобразования слова Р машиной Т обязательно указыва­ ется положение слова на ленте относительно читающей головки. Если 236