Остаток от деления на машине Тьюринга?

Question

[nimbus214]

подскажите как реализовать данную задачу, идей нет.

Comments

[Alexandroppolus]

в машине Тьюрига, насколько помню, есть лента с нулями и единицами, и на одной из ячеек находится указатель. Как выглядит начальный расклад для задачи?

[nimbus214]

Alexandroppolus, немного не понял вопроса, полагаю что так

[rundll32]

Возможно, пример алгоритма на Brainfuck будет наиболее приближен к ответу
https://esolangs.org/wiki/Brainfuck_algorithms#x_....
https://esolangs.org/wiki/Brainfuck_algorithms#Div...

[Денис Загаевский]

Alexandroppolus, нет, в машине Тьюринга произвольный алфавит. Очевидно, здесь он состоит из | и ÷ (и возможно ещё стрелки)

[nimbus214]

rundll32, для каких языков эти алгоритмы?

[Денис Загаевский]

nimbus214, написано же, для брейнфака. Не обращай внимания, человек просто не в теме. Брейнфак с МТ имеет мало общего.

[nimbus214]

Денис Загаевский, ага, спасибо, вот только как решать свою задачу, до сих пор не понимаю)

Answer 1

[Денис Загаевский]

В общем порекомендую сначала прикинуть алгоритм на естественном языке, в смысле, как бы это могло быть:
Встаем на %.
Пока в делителе есть 1, заменяем её на Х, и заменяем одну 1 в делимом на Y. Если в делимом нет единиц(нечего заменить на Y), то переносим все Y в виде 1 на ячейки после "->". Это и есть ответ.
Когда в делителе все 1 заменены на Х, заменяем их обратно на 1 и проверяем, остались ли ещё 1 в делимом.
Если в делимом остались единицы, заменяем все Y на 0, встаем на % и начинаем всё это заново.
Если в делимом единиц не осталось, то переносим все оставшиеся Y в виде 1 на ячейки после "->". Это и есть ответ.
Тут была ошибка. Мы только что успешно закончили отнимать очередной делитель, и в делимом больше ничего не осталось. Это значит, что разделилось нацело.

Не скажу, что это оптимально, но работать будет. Может быть , надо продумать ещё какие-то корнер кейсы, но идея должна быть понятна. По сути ты просто отнимаешь от делимого делитель до тех пор, пока делимое не станет меньше делителя.
Теперь каждое из этих правил надо оформить в виде набора правил для МТ. Всех этих "когда/если/то" в МТ конечно нет, поэтому придется эмулировать их переходами в соответствующее состояние. Это не сложно, но правил может получиться реально много. Например, простая фраза "Пока в делителе есть 1, заменяем её на Х, и заменяем одну 1 в делимом на Y." будет развернута в 3-5 состояний.

Плюс, этот алгоритм портит исходные данные. Если портить их нельзя, то надо сначала скопировать их в другое место на ленте, а потом не забыть "прибраться", удалив оставшийся мусор.

Comments

[Денис Загаевский]

Один корнер кейс не учёл - когда разделилось нацело. Нужно это проверить и закончить выполнение

[nimbus214]

Денис Загаевский, спасибо, всё доходчиво и понятно

[nimbus214]

Денис Загаевский, Привет, а как сделать проверку Y в знаменателе "Когда в делителе все 1 заменены на Х, заменяем их обратно на 1 и проверяем, остались ли ещё 1 в делимом." вот в этом моменте?

[Денис Загаевский]

nimbus214, ты будешь в некотором состоянии q. Видя в нём "->" переходишь в состояние p1, сдвигаясь влево.
q "->" -> p1 "->" L

p1 X -> p1 1 L
p1 % -> p2 % L

p2 0 -> p2 0 L // "отнимать" будем с конца, так проще, нет смысла ходить в начало. Поэтому будут встречаться нули.
p2 Y -> p3 Y L // начались Y-и. По построению они идут сплошняком до 0 или 1.
p3 0 -> n0 0 R // в делимом не осталось 1
n0 это начало ветки, когда разделилось нацело. Потому что мы только что закончили отнимать очередной делитель, отняли успешно, и больше в делимом ничего не осталось
p3 1 -> b0 1 R // в делимом остались единицы
b0 это "Если в делимом остались единицы, заменяем все Y на 0, встаем на % и начинаем всё это заново."
b0 0 -> b0 0 R
b0 Y -> b0 0 R
b0 % -> s % N // s - твоё стартовое состояние
n0 распиши сам.