Машина Тьюринга, добавляющая два числа

Question

Как я могу создать машину Тьюринга, которая будет вычислять сумму двух двоичных цифр, разделенных #, например. 111 # 101B, где B для бланка? Результат можно записать в конце ленты.

Answer 1

1. Напишите машину Тьюринга для преобразования обоих двоичных чисел в одинарные (сохраняя пробел между ними). ​​
2. Напишите машину Тьюринга, чтобы заменить бланк на 1, и отрубите цифру с конца.
3. Напишите машину Тьюринга для преобразования унарного числа в двоичное.
4. Сцепите эти три машины вместе.