Машина Тьюринга и рекурсивные функции. Кацаран Т.К - 10 стр.

                        § 2. Работа машины Тьюринга

     Работа машины полностью определяется заданием в первый (на-
чальный) момент: 1) слова на ленте, т. е. последовательности символов,
записанных в клетках ленты (слово получается чтением этих символов по
клеткам ленты слева направо); 2) положения головки; 3) внутреннего со-
стояния машины. Совокупность этих трех условий (в данный момент) на-
зывается конфигурацией (в данный момент). Обычно в начальный момент
внутренним состоянием машины является q1 , а головка находится либо
над первой слева, либо над первой справа клеткой ленты.
     Заданное слово на ленте с начальным состоянием q1 и положение
головки над первым словом называется начальной конфигурацией. В про-
тивном случае говорят, что машина Тьюринга не применима к слову на-
чальной конфигурации.
     Другими словами, в начальный момент конфигурация представима в
следующем виде: на ленте, состоящей из некоторого числа клеток, в каж-
дой клетке записан один из символов внешнего алфавита A , головка нахо-
дится над первой слева или первой справа клеткой ленты и внутренним со-
стоянием машины является q1 . Получившееся в результате реализации
этой команды слово на ленте и положение головки называется заключи-
тельной конфигурацией.
     Например, если в начальный момент на ленте записано слово
a1�a 2 a1a1 , то начальная конфигурация будет иметь вид:

                         a1      a2        �     a1        a1

                         q1

(под клеткой, над которой находится головка, указывается внутреннее со-
стояние машины).
                                      10