Применение машин Тьюринга к словам

Проиллюстрируем на примерах все введенные понятия, связанные с машинами Тьюринга.

Пример. Машина Тьюринга задается внешним алфавитом А = (0, 1, *} (как и в предыдущем примере 0 — символ пустой ячей­ки), алфавитом внутренних состояний Q ={q₀, q₁, q₂, q₃}и программой:

Посмотрим, как эта машина перерабатывает некоторые слова и постараемся обнаружить закономерность в ее работе.

Предварительно заметим, что программа машины может быть записана также в виде следующей таблицы. Чтобы определить по таблице, что будет делать машина, нахо­дясь, например, в состоянии q2 и наблюдая в обозреваемой ячей­ке символ 1, нужно найти в таблице клетку, находящуюся на пересечении столбца q2 и строки, содержащей 1.

В этой клетке записано q21Л. Это означает, что на следующем шаге машина останется в прежнем состоянии q2, сохранит содержимое обозреваемой ячейки 1 и перейдет к обозрению следующей левой ячейки на ленте.

Применим эту машину к слову 11*11. Вот последовательность конфигураций, возникающих в процессе работы машины (исход­ная конфигурация — стандартная начальная):

Нетрудно заметить, что данная машина Тьюринга реализует операцию сложения: в результате ее работы на ленте записано подряд столько единиц, сколько их было всего записано по обе стороны от звездочки перед началом работы машины.

Этот маленький опыт работы с машинами Тьюринга позволяет сделать некоторые выводы. Так тщательно описанное устройство этой машины (разбитая на ячейки лента, считывающая головка) по существу не имеет никакого значения. Машина Тьюринга — не что иное, как некоторое правило (алгоритм) для преобразования слов алфавита A U Q, т.е. конфигураций. Таким образом, для опре­деления машины Тьюринга нужно задать ее внешний и внутрен­ний алфавиты, программу и указать, какие из символов обознача­ют пустую ячейку и заключительное состояние.