Машины Тьюринга. Пример 7.8

Разглядим решение обсуждавшейся в прошлом параграфе задачки о добавлении 1 к унарному числу средством машины Тьюринга. Наружный алфавит может быть задан обилием А = {∆,1}, где 1 соответствует заполненной секции, а ∆ — пустому знаку, при этом заполненные следуют вереницей попорядку. Внутренний алфавит задается обилием Q = {q, z}, где q соответствует рабочему состоянию ЛУ, a z-остановке. Набор всех правил преобразования (логическая функция) может быть представлен многофункциональной схемой:

Составляется многофункциональная схема в виде таблицы таким макаром, что знаки, обозначающие колонки и строчки, определяют входные характеристики ЛУ, а в ячейке таблицы на их скрещении стоит выходная команда. А именно, если головка машины обозревает секцию ленты со знаком 1 и машина находится в рабочем состоянии (q), то результатом ее работе на данном такте должно стать повторение 1 в данной секции и переход на одну секцию на право R (при всем этом, как указывалось, лента двигается на лево) — эта команда записывается как q1R. Если же в обозреваемой секции ∆, а состояние ЛУ q, то ∆ будет заменен 1, сдвига ленты выполняться не будет и машина остановится – z1S. При композиции на входе ∆z, как и 1z, машина находится в нерабочем состоянии — не происходит ни конфигурации конфигурации, ни движения — по этой причине такие композиции в многофункциональных схемах в предстоящем отображаться не будут.

Пусть исходной является конфигурация 1q1111*. Тогда работа машины в согласовании с описанной логической функции будет происходить последующим образом:

*Как указывалось выше, незначащие пустые секции слева и справа от заполненных в конфигурацию не врубаются; так как в данной задачке несколько заполненных секций следуют попорядку, только они и указываются в конфигурации.

Такт 1 Обозревается 1, в ЛУ состояние q. Выходная команда q1R, что эквивалентно перемещению головки по отношению ленты на 1 шаг на право. Как следует, появляется промежуточная конфигурация 11 q111.

Такт 2 — аналогичным образом осуществляется переход к конфигурации 111q11.

Такт 3 — переход к конфигурации 1111q1.

Такт 4 — переход к конфигурации 11111q∆ (тут для наилучшего осознания правый ∆ указан в очевидном виде).

Такт 5 Обозревается ∆, в ЛУ состояние q. Выходная команда z1S — заместо ∆ в ячейку записывается 1, сдвига нет, работа прекращается. Конечная конфигурация 111111z.

Задачка решена.