Математическая логика и теория алгоритмов. Сергиевская И.М. - 49 стр.

прекратить работу и в случае, когда в программе отсутствует команда для
некоторого состояния и некоторого символа.
      Если машина Тьюринга T , начав работу на некотором слове P ,
останавливается через некоторое число шагов, то считается, что она применима к
слову P . Результатом применения машины к слову является слово T (P) , которое
соответствует заключительной конфигурации. Если же машина, начав работу на
слове P , никогда не останавливается, то говорят, что она не применима к слову P .

     Пример. Пусть машина Тьюринга задана программой:
        ⎧q1 0q0 1E
     T :⎨          .
        ⎩q11q11R
     Рассмотрим записанные в последовательных n ячейках n единиц.
     Пусть, например, начальная конфигурация имеет вид:
     q1111K11 .
     Сокращенно эту конфигурацию можно записать так:
     q11n .
       Вообще, записанные подряд n единиц обозначаются 1n , а записанные подряд
m нулей – 0 m .
       Тогда в каждом такте машина Тьюринга будет оставлять обозреваемую
единицу на месте и сдвигаться вправо на одну ячейку. Процесс будет продолжаться
до тех пор, пока управляющая головка не выйдет на пустую ячейку (0). Здесь,
согласно программе, в ячейку будет вписана единица, и машина остановится. В
результате на ленте будет записано n+1 единиц. Если условиться, что исходное
слово выражает число n, то можно считать, что машина вычисляет функцию
ϕ (n) = n + 1 .

       Пример. Дана машина Тьюринга:
           ⎧q1 0q1 0 R
           ⎪
       T : ⎨q11q 2 0 R .
           ⎪q 1q 0 R
           ⎩ 2 1
Выяснить, применима ли машина к слову P :
а) P = 1301 ; б) P = 16 .
Если применима, то выписать результат T (P) применения машины T к слову P .
Предполагается, что в начальный момент времени головка машины обозревает
самую левую единицу слова.
       Решение. а) Применяя машину T к слову P , получаем последовательность
конфигураций:
   1) q11301 .            3) q1101 .
   2) q212 01 .           4) q2 01 .
     Вид второй конфигурации обусловлен тем, что символ 0 считается пустым
символом и может не записываться.


                                        54