Пример 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.

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

Пример 9.4

Пример 4.9

A.3. Условная вероятность

Информация и алфавит

Нормальные алгоритмы Маркова

Вернуться в оглавление: Теоретические основы информатики