Как построить машину Тьюринга для умножения десятичного числа на 11?

Question

[ZIK1337]

Используется алфавит A={0,1,2,⋯,9}. Нужно построить таблицу машины Тьюринга, которая умножает входное слово на 11.

Понятно, что последовательность такая:
1) Проверка, не равно ли нулю входное слово или не пустое ли оно, одновременно удаляя незначащие нули
2) Добавление 0 в конец, и после добавление "+"
3) Копирование справа от "+" входного слова без добавленного нуля
4) Сложение

Вопрос, как сделать это копирование нормально для десятичного числа?
Для 10 цифр это уже 10 состояний, а после записи нужно еще вернуться и восстановить заменённый символ обратно, получается еще 10 символов добавлять для каждой цифры (иначе как понять, на что восстанавливать)?
Кажется, перебор

Может нужно как-то по-другому?

Comments

[NazikMGE]

Знаю что опоздал ответить, просто у самого была такая задача недавно в универе, я решил ее и вот решил поделиться
решения удачи вам в учебе.

[NazikMGE]

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

[ZIK1337]

очень опоздали, я уже закончил учебу, да и задачу тоже решил тогда, причем все в бумажном виде

Answer 1

[Rsa97]

Примем, что в исходном положении каретка стоит на последней цифре числа.
У нас будут состояния от q₀ до q₁₀, соответствующие сумме младшего разряда исходного числа и переноса из него . Начальное состояние - q₀.
q_ia_j → q_{((i + j) div 10) + j}a_{(i + j % 10)}L,
q_{i ≠ 0}ε → q_{(i div 10)}a_{(i % 10)}L,
q₀ε → q_stop,
где div - целочисленное деление.
Теперь каретка стоит в пустой клетке перед результатом.

Comments

[ZIK1337]

Div и mod реализовать это еще та задача, может выйти еще больше состояний.
Каретка под первым символом входного слова у меня, не проблема, конечно, перенести под последний, просто для уточнения.

[Rsa97]

ZIK1337, По этим шаблонам строится весь набор правил для умножения на 11. Просто перебираете i от 0 до 10 и j от 0 до 9 + ε и получаете 121 правило.
Например, для состояния q₅ и символа a₇ получим правило
q₅a₇ → q_{((5 + 7) div 10) + 7}a_{(5 + 7) % 10}L = q₈a₂L

[ZIK1337]

Rsa97, а алгоритм умножения на 11, где первая и последняя цифры сохраняются, а между ними суммы каждой пары чисел - легче не будет?

[Rsa97]

Последняя цифра и в этом алгоритме сохраняется.
А с чего бы первой цифре сохраняться? Например 99*11 = 1089.

[ZIK1337]

Rsa97, ну когда сумма больше 10, там по-другому, это понятно