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

1нутренним состоянием обладает каждая машина и называется ючальным состоянием. Машина имеет читающую головку, которая в каждый данный юмент времени находится на одном из квадратов ленты и воспри- шмает символ, записанный на этом квадрате. Будем предполагать, !то среди символов SO,S],..,S „ имеется символ, означающий пустой свадрат, например, So. Положим, что символ S Q принадлежит алфавиту саждой машины Тьюринга и So не может быть записан ни в каком свадрате ленты. Когда пишем, что читающая головка обозревает свадрат с символом S Q или записывает в квадрат символ So, то имеем } виду, что читающая головка соответственно обозревает пустой свадрат (воспринимая его как So) или оставляет квадрат без символов воспринимая его как S Q). Машина действует не непрерывно, а лишь 3 дискретные моменты времени. Если в какой-то момент времени t читающая головка воспри- ^имaeт квадрат (т.е. стоит на квадрате), содержащий символ Sj, i машина находится во внутреннем состоянии qj, то действие машины определено, и она совершает одно из следующих четырех действий: Г) головка стирает символ Si и записывает на том же квадрате лшвол Sk, 2) головка перемещается в соседний слева квадрат; 3) головка перемещается в соседний справа квадрат; 4) машина останавливается. В случаях 1)-3) машина переходит во внутреннее состояние и готова к действию в следующий момент времени /+1. Первые три из возможных актов действия машины могут быть описаны соответственно следующими упорядоченными четверками символов, которые в дальнейшем будем называть командами; 1) qj Sf Sji q/, 2) q. Si L q,.-, 3) qjSiRqr. Любая машина имеет конечное (непустое) множество команд. 235