Определить результат применения машины Тьюринга с заданной программой к данному слову: …Λ101Λ…. Бесплатный доступ к контрольной работе

Реферат.Справочник
Контрольные работы по высшей математике
Определить результат применения машины Тьюринга с заданной программой к данному слову: …Λ101Λ…

Определить результат применения машины Тьюринга с заданной программой к данному слову: …Λ101Λ… .pdf

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

Условие

Определить результат применения машины Тьюринга с заданной программой к данному слову: …Λ101Λ… q1 q2 Λ 1q2 0Rq0 0 1Rq1 1Lq2 1 0Rq1 0Lq2 В начальный момент головка обозревает крайнюю левую непустую ячейку.

Решение

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

Будем подписывать состояние машины Тьюринга под рассматриваемым символом строки (Λ – пустой символ, R,L – направление движения):
Λ1q101Λ→Λ00q11Λ→Λ011q1Λ→Λ010Λq1→Λ0101q2Λ→Λ010q20Λ→Λ01q210Λ→
→Λ0q2010Λ→Λq21010Λ→Λ01q0010Λ
Перешли в конечное состояние q0

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

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

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