Составить программу реализующую машину Тьюринга, вычисляющую значение данной функции 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
Решение
Итак, начальное состояние ленты МТ — …a01x01ya0…, где a0 — символ пустой ячейки, 1x — 1…1x раз, при этом полагаем 10 — 0. Будем считать q1 — начальное состояние МТ, q0 — заключительное состояние МТ. Команда имеет вид qiaj→qkalM, где i≠0, M — один из трёх символов движения: L — «влево на одну ячейку», R — «вправо на одну ячейку», S — «на месте»; смысл команды qiaj→qkalM — находясь в состоянии qi и обозревая в текущей ячейке символ aj МТ переходит в состояние qk, вписывает в текущую ячейку символ al и осуществляет соответствующий сдвиг. Для наших целей удобно считать, что МТ начинает работу находясь на разделительном 0 (в противном случае этого всегда можно добиться, сдвинувшись на нужное количество ячеек вправо или влево). Если слева от центрального нуля стоит ноль (x=0) то требуется оставить на ленте 0 (0∸3y=0 при любом значении y); если же x≠0, то сначала нужно умножить x на 5 а y на 3, а затем выполнить 5x∸3y.
q10→q20L
Начало
q20→q3a0R
x=0
q30→q3a0R
«обнуление» ленты
q31→q3a0R
q3a0→q00S
0∸3y=0 и остановка
q21→q21L
x≠0, двигаемся влево
q2a0→q4a0R
находимся в начале 1-го аргумента
q41→q5*L
меняем 1 (если ещё есть) 1-го аргумента на вспомогательный символ *
q5*→q5*L
двигаемся влево до пустой ячейки
q51→q51L
q5a0→q61L
добавляем четыре единицы (на каждую 1 первого аргумента)
q6a0→q71L
q7a0→q81L
q8a0→q91R
q91→q91R
двигаемся вправо пропуская добавленные тройки единиц
q9*→q10*R
двигаемся вправо пропуская *
q10*→q10*R
q101→q41S
дойдя до 1 повторяем цикл
q100→q110L
все единицы 1-го аргумента исчерпаны, переходим к восстановлению
q11*→q111L
восстанавливаем заменённые единицы
q111→q121R
восстановление закончено
q121→q121R
двигаемся вправо к разделительному нулю
q120→q130R
переходим ко 2-му аргументу
q130→q14a0L
1-й аргумент равен нулю, стираем ненужные нули
q141→q01S
конец работы при x=0
q131→q131R
y≠0, переходим на конец 2-го аргумента
q13a0→q151L
находимся на конце 2-го аргумента
q151→q16*R
меняем 1 (если ещё есть) 2-го аргумента на вспомогательный символ *
q16*→q16*R
двигаемся влево до пустой ячейки
q161→q161R
q16a0→q171R
добавляем две единицы (на каждую единицу 2-го аргумента)
q17a0→q181L
q181→q181L
двигаемся влево пропуская добавленные двойки единиц
q18*→q19*L
двигаемся вправо пропуская *
q19*→q19*L
q191→q151S
дойдя до 1 повторяем цикл
q190→q200R
все единицы 2-го аргумента исчерпаны, переходим к восстановлению
q20*→q201R
восстанавливаем заменённые единицы
q201→q201R
восстановление закончено, движемся вправо к концу 3y
q20a0→q21a0L
находимся в конце 2-го аргумента, переходим к вычитанию
q211→q22a0L
в состоянии q21 стираем единицы 2-го аргумента
q221→q221L
в состоянии q22 двигаемся до начала 1-го аргумента
q220→q220L
q22a0→q23a0R
находимся в начале 1-го аргумента
q231→q24a0R
в состоянии q23 стираем единицы 1-го аргумента
q241→q241R
в состоянии q24 двигаемся в конец 2-го аргумента
q240→q240R
q24a0→q21a0L
цикл вычитания
q210→q250L
МТ в состоянии q21 на нуле, 5x≥3y, нужна дополнительная проверка
q25a0→q0a0R
МТ в состоянии q25 на a0, 5x=3y, на ленте 0 конец работы
q251→q251R
МТ в состоянии q25 на 1, 5x>3y, требуется удалить 0
q250→q0a0S
конец работы при 5x>3y
q230→q26a0R
МТ в состоянии q23 на нуле, 5x<3y, требуется «обнулить» ленту
q261→q26a0R
«обнуление» ленты
q26a0→q00S
конец работы при 5x<3y
Задать вопрос
на новый заказ в Автор24.
