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

Реферат.Справочник
Решенные задачи по другому
По аналогии с предыдущей задачей составьте функциональную схему машины Тьюринга

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

Зарегистрируйся в 2 клика в Кампус и получи неограниченный доступ к материалам с подпиской Кампус+ 🔥

Условие

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

Решение

Потяни, чтобы посмотреть

В качестве внешнего алфавита естественно выбрать алфавит, содержащий наименование всех цифр десятичной системы счисления и пустой символ a0, т.е. A = {a0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0}.
Состояний у машины будет пять: q0 – остановка, q1, q2, q3, q4 – рабочие состояния, т.е . Q = {q0, q1, q2, q3, q4}.
Функциональная схема (программа) машины:
q1 i → q0 (i - 1) (для i = 1, 2, …, 9),
q1 0 → q2 9Л,
q1 a0→ q0 a0,
q2 i → q0 (i - 1) (для i = 2, …, 9),
q2 0 → q2 9Л,
q2 1 → q3 0Л,
q2 a0 → q0 a0,
q3 i → q0 i, (для i = 0, 1, 2, …, 9),
q3 a0 → q4 a0П,
q4 0 → q0 a0
Начальное положение машины стандартное.
Приведем последовательности конфигураций, получаемых при переработке этой машиной слов.
3: a0q13a0 → a0q02a0
297: a029q17a0 → a029q06a0
10: a01q10a0 → a0q219a0 → q3a009a0 → a0q409a0→ a0q0a09a0
100: a010q10a0 → a01q209a0 → a0q2199a0 → q3a0099a0 →
a0q4099a0 → a0q0a099a0
120: a012q10a0 → a01q229a0 → a01q019a0

50% задачи недоступно для прочтения

Переходи в Кампус, регистрируйся и получай полное решение

Получить задачу