Алгоритм для машины Тьюринга для переноса числа влево

Вычитай из левого и правого чисел по единице - пока правое число не закончится.

Если при движении вправо мы дошли до '-' и следующим после минуса символом стоит 0 - удаляем этот 0, сдвигая все следующие за ним символы числа на 1 позицию влево. И только после этого либо вычитаем из правого числа единицу (если справа от '-' есть цифры), либо удаляем '-' и останавливаемся (если справа от '-' пустая ячейка).

Т.е. если было -100, то при удалении 1 получим -099, при следующем заходе сначала из -099 получим -99 и уже из него удалим 1.

Второй вариант: ничего не удаляем, но когда движемся по правому числу, проверяем его цифры. Если все цифры '0' - стираем правое число и заканчиваем работу. Если же хотя бы одна цифра не '0' - вычитаем единицу и продолжаем работу.

Т.е. сначала из -100 получим -099, позже из -010 получим -009 и когда достигнем -000, сотрём его и остановимся.

Для решения данной проблемы можно использовать следующий алгоритм на машине Тьюринга:

Найти разряд, в котором произойдет вычитание.
Если разряд уменьшаемого числа больше или равен разряду вычитаемого числа, то вычесть соответствующие цифры и перейти к шагу 5.
Если разряд уменьшаемого числа меньше разряда вычитаемого числа, то перенести число из ячейки справа от уменьшаемого числа в ячейку слева от вычитаемого числа.
Повторить шаг 2.
Перейти к следующему разряду и повторить шаги с 2 по 5 до тех пор, пока все разряды не будут обработаны.
Таким образом, если при вычитании из числа справа пропадает левый разряд, то алгоритм автоматически перенесет это число влево на одну ячейку и продолжит работу.

Прочитать эту статью