Сконструируйте машину Тьюринга с внешним алфавитом A={a0}. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по другому
Сконструируйте машину Тьюринга с внешним алфавитом A={a0}

Сконструируйте машину Тьюринга с внешним алфавитом A={a0} .pdf

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

Условие

Сконструируйте машину Тьюринга с внешним алфавитом A={a0,1}, которая каждое слово длиной n в алфавите A1={1} перерабатывает в слово длиной n+1 в том же алфавите A.

Решение

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

Пусть внешний алфавит машины Тьюринга A={a0,1}.
Состояний у машины будет два: q0 – остановка, q1 – рабочее состояние, т.е . Q={q0, q1}.
Функциональная схема (программа) машины:
q11 → q11П, q1 a0 → q0 1.
Начальное положение машины стандартное.
Приведем последовательности конфигураций, получаемых при переработке этой машиной слов.
1 (n=1): a0q11a0 → a01q1a0 → a01q01
111 (n=3): a011q11a0 → a0111q1a0 → a0111q01

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

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

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