Машина Тьюринга (целая часть от деления)

Деление нацело любых натуральных чисел на машине Тьюринга (оба числа записаны на ленте последовательностью единиц такой длины каково число)? Это довольно сложная задача.

Деление делается через вычитание. При вычитании вычитаемое уничтожается, значит надо еще уметь делать копию числа. Кроме того, на ленте нужно место для результата деления.

Идея алгоритма такая.

1)копируем делитель к делимому,

2)производим вычитание этой копии из делимого.

3)если вычлось, то добавляем 1 к результату деления.

Потом опять переходим на шаг (в состояние) 1. Так делаем до тех пор, пока удаётся вычитать. Если вычесть не удалось, то очищаем на ленте всё, кроме результата деления.

Добавлено через 50 минут

Вот для примера

НАМ для деления двух чисел