Условие задачи
Составить программу реализующую машину Тьюринга, вычисляющую значение данной функции f(x,y). Числа x,y>0 соответствуют на ленте наборам из x и y единиц соответственно. Наборы единиц разделять нулем.
Переменные x и y могут равняться нулю. Например, набор 000 означает, что x=0, y=0, а набор 00111 соответствует значениям x=0, y=3.
Если функция не определена при каких-то значениях x и y, то программа должна выдавать 0. Первый набор единиц — значение x, второй — значение y.
f(x,y)=4y∸x
Ответ
Итак, начальное состояние ленты МТ a0 1x 01y a0, где a0 символ пустой ячейки, 1x , при этом полагаем 10 0. Будем считать q1 начальное состояние МТ, q0 заключительное состояние МТ. Команда имеет вид qiajqkalM, где i0, M один из трёх символов движения: L влево на одну ячейку, R вправо на одну ячейку, S на месте; смысл команды qiajqkalM находясь в состоянии qi и обозревая в текущей ячейке символ aj МТ переходит в состояние qk, вписывает в текущую ячейку символ al и осуществляет соответствующий сдвиг. Для наших целей удобно считать, что МТ начинает работу находясь на разделительном 0 (в...
