Узнать стоимость написания работы
Оставьте заявку, и в течение 5 минут на почту вам станут поступать предложения!
Ответы на вопросы

Конспект лекций по предмету "Информатика"


Пример 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.
Задача решена.


Не сдавайте скачаную работу преподавателю!
Данный конспект лекций Вы можете использовать для создания шпаргалок и подготовки к экзаменам.

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем конспект самостоятельно:
! Как написать конспект Как правильно подойти к написанию чтобы быстро и информативно все зафиксировать.