How to build a Turing machine to multiply a decimal number by 11?

Question

Algorithms

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

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

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

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

Answer 1

Let's assume that in the initial position the caret is on the last digit of the number.
We will have states from q ₀ to q ₁₀ corresponding to the sum of the least significant digit of the original number and the transfer from it. The initial state is q ₀ .
q _i a _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 ,
where div is an integer division.
Now the caret is in an empty cell in front of the result.