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

что символ So принадлежит алфавиту каждой машины Тьюринга и So не может быть записан ни в каком квадрате ленты. Когда пишем, что читаюш,ая головка обозревает квадрат с символом So или записывает в квадрат символ So, то имеем в виду, что читаюш,ая головка соответственно обозревает пустой квадрат (воспринимая его как So) или оставляет квадрат без символов (воспринимая его как So). Машина действует не непрерывно, а лишь в дискретные моменты времени. Если в какой-то момент времени t читаюш,ая головка воспринимает квадрат (т.е. стоит на квадрате), содержащий символ Si, и машина находится во внутреннем состоянии qj, то действие машины определено, и она совершает одно из следуюш,их четырех действий: 1) головка стирает символ Si и записывает на том же квадрате символ Sk, 2) головка перемещается в соседний слева квадрат; 3) головка перемещается в соседний справа квадрат; 4) машина останавливается. В случаях 1)-3) машина переходит во внутреннее состояние qr и готова к действию в следующий момент времени t+\. Первые три из возможных актов действия машины могут быть описаны соответственно следующими упорядоченными четверками символов, которые в дальнейшем будем называть командами: 1) qj Si Sj( q^, 2) QJ SI L QY, 3) QJ SI R QR. Любая машина имеет конечное (непустое) множество команд. Машина останавливается, если она находится в некотором внутреннем состоянии qj, читающая головка обозревает какой-то символ Sk, а среди команд машины нет команды, начинающейся с qjSk. Если на ленте имеется какое-нибудь слово Р (в частности, пустое слово), читающая головка помещена на квадрат с первой левой буквой слова Р и машина приведена во внутреннее состояние qo, то машина начинает оперировать на ленте: ее головка стирает и пишет символы и перемещается из одного квадрата в другой (соседний). Если при этом машина когда-нибудь останавливается, то находящееся в момент остановки слово на ленте считается результатом применения машины Т к данному слову Р. Если процесс переработки машиной Т слова Р бесконечен, то говорят, что машина Т не применима к слову Р. 158