Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

§ 8. Задание машины Тьюринга Машина Тьюринга Т считается заданной, если задано непустое конечное множество упорядоченных четверок символов (команд), удовлетворяющих условиям: а) каждая команда (четверка символов) принадлежит к одному из трех типов команд, приведенных в § 7; б) никакие две команды одной машины не имеют совпадаюш,ие первые два символа; в) среди команд любой машины всегда есть хотя бы одна команда, начинающаяся с qo. Множество всех символов типа Sm, входящих в команды машины, называется алфавитом заданной машины, а входящие в эти команды символы qi называются внутренними состояниями заданной машины Т. Считаем, что в исходном (начальном) состоянии машина обладает внутренним состоянием qo. Для преобразования слова Р машиной Т обязательно указывается положение слова на ленте относительно читающей головки. Если это не сделано, то предполагается, что читающая головка находится на первой (самой левой) букве слова Р. Рассмотрим несколько примеров. 1. Пусть задана машина Т командами: — — — Г П — — — — Г ^olRqi — — — — qiSolqo а на ленте записано слово Р=1, см. Рис. 5.5. qo Легко убедиться, что машина Т, начав Рис. 5.5. работу с первой буквы слова Р, приписывает к нему слева по одной букве 1 на каждом шаге, никогда при этом не останавливаясь. Следовательно, эта машина неприменима к слову Р. 2. Машина, заданная командами: qoSoRqo qoSiRqo qoS2Rqo qoSkRqo qollqi где ни одно из Si (l<i<k) не совпадает с символом 7, движется по ленте вправо, пока не встретит вхождение (если такое вообще имеется) символа 7, после чего останавливается. 3. Машина Т, заданная командами 159