Составить программу реализующую машину Тьюринга. Бесплатный доступ к контрольной работе

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

Составить программу реализующую машину Тьюринга .pdf

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

Условие

Составить программу реализующую машину Тьюринга, вычисляющую значение данной функции f(x,y). Числа x,y>0 соответствуют на ленте наборам из x и y единиц соответственно. Наборы единиц разделять нулем. fx,y=5y∸2x.

Нужно полное решение этой работы?

Решение

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

Рассматривается усеченное вычитание вида 15y+1-12x+1, которое начинается с 5y циклов, в результате каждого из которых стираются крайние единицы содержимого ленты. Начальное состояния q1 поддерживает перемещение головки вправо до разделителя «0»:
…0q115y+1-12x+10… ⟹ …015y+1-12x+1q10…
Затем в состоянии q2 стирается самая правая единица и в состоянии q3 происходит перемещение головки влево до разделителя 0:
…015y+1-12x+1q10… ⟹ …015y+1-12xq20… ⟹ …015y+1-12x-1q310… ⟹ …015y+1-q312x0… ⟹ …0q3015y+1-12x0…
Затем в состоянии q4 стирается самая левая единица и начинается второй цикл: в состоянии q1 повторяется перемещение головки право до разделителя 0 и т.д.:
…q3015y+1-12x0… ⟹ …0q415y+1-12x0… ⟹ …0q115y-12x0…
Последний цикл отличается тем, что, обозревая символ «–» в состоянии q2, головка заменяет его на «1» и переходит в состояние q5, обеспечивающее корректное завершение программы:
…0q115y-2x-0… ⟹ …015y-2xq1-0… ⟹ …015y-2x-q10… ⟹ …015y-2xq2-0… ⟹ …0q515y-2x10 ⟹ …q5015y-2x+10… ⟹ …q015y-2x+10…
Необходимо также предусмотреть условие, когда вычитаемое больше уменьшаемого (состояние q6)

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

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

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