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

Доказательство. Каждая конкретная машина Тьюринга содер­ жит конечное число команд вида 1)-3) {§ 7). Выпишем сначала для всех команд вида qjSfSkqr (если они есть) машины Т формулы подста­ новки qjSr^q,Sk. При этом порядок этих формул подстановок друг относительно друга не существенен, ибо никакие две команды машины Т не имели совпадающими первые два символа. Далее для каждой команды вида qjSjLqr (если она есть) выпишем всевозможные формулы подстановки вида Siqfir^q^iS), где Si&A, и формулу подстановки qjSr^qrSoSi. Затем для каждой команды вида qjSfRqr (если она есть) выпишем всевозможные формулы подстановки qjS,Si —^iqrSi, где S I E A , И формулу подстановки qjSj-^SiqrSo- Наконец, выпишем всевозможные формулы подстановок где q; - внутреннее состояние заданной машины Т, и формулу подстановки A-^qo. Полученная таким образом таблица (схема) формул подстановок определяет некоторый нормальный алгоритм В надА . Покажем, что полученный нормальный алгоритм В вполне эквивалентен относительно алфавита ^4 алгоритму Тьюринга Лт;^!, т.е. оба алгоритма одинаковым образом преобразуют любое слово Р алфавита А . Для этого возьмем произвольное слово Р в алфавите А, пусть, например, P=Ski,Skb"-Sia „, где Sici^A. Машина Тьюринга нахо­ дится сначала во внутреннем состоянии qo и обозревает символ Sk]. Дальнейшие ее действия определены ее командами. Из подстановок алгоритма В к слову Р будет сначала применима только последняя подстановка, в результате которой получим слово qo SiihSk2,---nSkm • (6.2) Если среди команд машины Т имеется команда, по которой стирается буква Ski и заменяется, например, буквой S j { S j e A ) , т.е. имеется команда qaSkiSjq,, то по подстановке q^Ski-^qrSj алгоритм преобразует слово (6.2) в слово qr SjSk2...Skm- 240