Постройте машину Тьюринга перерабатывающую слово 01x (в слове x единиц) в это же слово 01x0 из стандартного начального положения. Бесплатный доступ к решению задач

Реферат.Справочник
Решенные задачи по другому
Постройте машину Тьюринга перерабатывающую слово 01x (в слове x единиц) в это же слово 01x0 из стандартного начального положения

Постройте машину Тьюринга перерабатывающую слово 01x (в слове x единиц) в это же слово 01x0 из стандартного начального положения .pdf

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

Условие

Постройте машину Тьюринга, перерабатывающую слово 01x (в слове x единиц) в это же слово 01x0 из стандартного начального положения, причем в момент остановки должна обозревается крайняя левая ячейка. (Эта машина называется «левый сдвиг» и обозначается Б-).

Решение

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

Пусть внешний алфавит машины Тьюринга A={a0, 0,1}.
Состояний у машины будет три: q0 – остановка, q1, q2 – рабочие состояния, т.е . Q = {q0, q1, q2}.
Функциональная схема (программа) машины:
q11 → q11П,
q1 a0 → q2 0Л,
q2 1 → q2 1Л,
q2 0 → q0 0.
Начальное положение машины стандартное.
Приведем последовательность конфигураций, получаемых при переработке этой машиной слова 01111 (014):
0111q11 → 01111q1a0 → 0111 q210 → 011 q2110 → 01 q21110
→ 0 q211110 → q2 011110 → q0 011110

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

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

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