Ср. Июн 5th, 2024

Разглядим решение обсуждавшейся в прошлом параграфе задачки о добавлении 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.

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

От content

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Ads Blocker Image Powered by Code Help Pro

Обнаружен блокировщик рекламы! Пожалуйста, обратите внимание на эту информацию.

We\'ve detected that you are using AdBlock or some other adblocking software which is preventing the page from fully loading.

У нас нет баннеров, флэшей, анимации, отвратительных звуков или всплывающих объявлений. Мы не реализовываем эти типы надоедливых объявлений! Нам нужны деньги для обслуживания сайта, и почти все они приходят от нашей интернет-рекламы.

Пожалуйста, добавьте tehnar.info к вашему белому списку блокирования объявлений или отключите программное обеспечение, блокирующее рекламу.

Powered By
100% Free SEO Tools - Tool Kits PRO