Даны два натуральных числа n и m, заданных в унарной системе счисления. Числа n и m представлены наборами символов « | », разделенных « \ ». В конце набора стоит «=». Разработать машину Тьюринга, которая будет производить деление нацело двух натуральных чисел n и m и находить остаток от деления. При этом результат должен быть записан следующим образом: после «=» должен находиться набор символов « | » частного (он может быть и пустым), после чего ставится знак «(», за которым следует набор символов « | » остатка от деления n на m.
Так, число 1 в унарной системе записывается как "|", число 2 - "||" и так далее.
Теперь обратимся к самой задаче. Для решения мы будем использовать машину Тьюринга - это абстрактное устройство в виде последовательности состояний, на каждом шаге которого происходит определенное действие. Такая машина может решать различные задачи, в данном случае - деление нацело двух унарных чисел.
1. Начинаем с состояния S1.
2. Проверяем, является ли число n большим или равным числу m, например, сравнивая количество символов "|".
- Если m > n (то есть число n меньше числа m), мы переходим в S5.
- Если m <= n, мы переходим в S2.
3. В состоянии S2 мы удаляем из числа n столько символов "|", сколько содержит число m. Записываем результат справа от преобразованного числа n.
4. Переходим в состояние S3.
5. Удаляем символ "\" после числа m и переходим в состояние S4.
6. В состоянии S4 мы возвращаемся к состоянию S1 для повторного выполнения шагов 2-5 до тех пор, пока n < m.
7. Когда n становится меньше m (то есть мы прошли по циклу S1-S2-S3-S4 несколько раз и n стало меньше m) или n становится пустым (в случае, если n делится нацело на m), переходим в S5.
8. В состоянии S5 записываем символ "=", после которого следует набор символов "|" частного и знак "(", после которого следует набор символов "|" остатка от деления n на m.
9. Заканчиваем выполнение.
Надеюсь, что все стало понятно. Если у тебя есть какие-то вопросы, не стесняйся задавать!