Умножить два двоичных числа в машине Тьюринга

Question

Я пытаюсь записать умножение двух двоичных чисел, используя машину Тьюринга. Я попытался скопировать множитель и после каждого добавления вычесть из него 1 (например, 110 * 110 = 110 + 110 // 110 - 001 и далее до второй итерации). Но я думаю, что есть гораздо более простой алгоритм, который я не могу найти. Если это важно, я использую этот симулятор

Answer 1

Вы можете использовать смещения. Операция 110 * 110 равна сумме 110 * 100 + 110 * 10.

Скажем, ваша реализация устанавливает длину параметров в 3 бита; подготовить место результата (не более 6 бит). Затем l oop над битами одного параметра и, если они равны 1, добавьте второй параметр к вашему результату с соответствующим смещением.

Вы прочитали первый бит первого параметра, это 0, вы пишете ничего, и ваш результат остается 000000.

Вы читаете второй бит, это 1. Вы добавляете свой второй параметр к своему результату со смещением 1, поэтому он равен 110, но записывается на один бит слева, тогда ваш результат будет 00 110 0.

Вы прочитали третий бит, он тоже равен 1. Вы снова добавляете свой второй параметр к своему результату, на этот раз со смещением 2, поэтому он сдвигается на 110 бит на два бита влево. Ваш результат становится 001100 + 0 110 00 = 100100.