Разглядим решение обсуждавшейся в прошлом параграфе задачки о добавлении 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.
Задачка решена.
Если основа оригинала (карты пли плана) прозрачна, то копию можно снять при помощи стола со…
Определение координат точки. Пусть точка А (рис. 32) находится в квадрате, абсциссы и ординаты вершин…
Рельефом местности называется совокупность неровностей физической поверхности земли. В зависимости от характера рельефа местность делят…
Для обозначения на планах и картах различных предметов местности, применяются специально разработанные условные знаки. Для обличения…
В инженерной геодезии чаще всего пользуются топографическими картами. Их составляют в масштабах 1:10000, 1:25000, 1:50000…