Вам необходимо реализовать полный сумматор . Этот вопрос, вероятно, домашнее задание, поэтому я предоставлю общий обзор. Машина Тьюринга M имеет особые состояния Q(xyc), где x,y ∈ {0,1,U} и c ∈ {0,1}. Состояние Q(xyc) означает, что i th бит X равен x, i th бит Y равен y, а перенос - c. Символ U означает, что бит i th соответствующих входов неизвестен. Состояния Q(Uyc), где y ∈ {0,1} недопустимы, потому что i th бит X известен, если известен i th бит Y. Алгоритм выглядит примерно так:
- Начальное состояние
M равно Q(UU0). - Предположим, что i th битов
X и Y добавляются, и перенос составляет c. Тогда M находится в состоянии Q(UUc). Если i больше, чем число битов в X и Y, перейдите к шагу (6). Поскольку младшие значащие входные биты перезаписываются на этапах (3) и (4), это условие легко обнаружить. - Найти младший значащий бит
x из X, перезаписать x с помощью $ и переход в состояние Q(xUc). - Найти младший значащий бит
y из Y, перезаписать y с помощью * и перейти в состояние Q(xyc). - Запишите соответствующую сумму в конце ленты, перейдите в состояние
Q(UUd), где d - новый перенос, и перейдите к шагу (2). Эти значения задаются таблицей истинности в приведенной выше ссылке. - Если
c = 1, напишите c в конце ленты. - Скопируйте обратную сторону вычисленного значения в начало ленты. Очистите оставшуюся ленту.
Обратите внимание, что вывод построен в обратном порядке и, следовательно, должен быть обращен на шаге (7). Оставшаяся работа состоит из написания состояний и переходов для перемещения / манипулирования лентой.