Логотип Автор24реферат
Задать вопрос
%
уникальность
не проверялась
Решение задач на тему:

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

уникальность
не проверялась
Аа
574 символов
Категория
Другое
Решение задач
Сконструируйте машину Тьюринга с внешним алфавитом 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% задачи недоступно для прочтения
Переходи в Кампус, регистрируйся и получай полное решение
Получить задачу
Больше решений задач по другому:
Все Решенные задачи по другому
Найди решение своей задачи среди 1 000 000 ответов
Крупнейшая русскоязычная библиотека студенческих решенных задач