_23.3. Алгоритм сложения.
Пусть даны два натуральных числа, записанных в унарной форме.
В памяти машины Тьюринга они будут разделены знаком +. На ленту подается пара чисел, например,
_1.0
-----------------------------------------
¦ ^ ¦ ^ ¦ ^ ¦ ¦ ¦ ¦ ¦ + ¦ ¦ ¦ ¦ ¦ ¦ ¦ ^ ¦
-----------------------------------------
_1.5
В результате должна получиться их сумма, в данном случае
_1.0
-----------------------------------------
¦ ^ ¦ ^ ¦ ^ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ^ ¦
-----------------------------------------
_1.5
Заметим, что работу машины нельзя свести к стиранию +, ибо тогда возникает пустая ячейка между палочками, а, следовательно, совокупность оставшихся палочек нельзя будет рассматривать как изображение одного натурального числа.
_3Функциональная схема:
_1.0
+--------------------------+
¦ ¦ q1 ¦ q2 ¦ q3 ¦
¦-----+------+------+------¦
¦ ¦ ¦ ^Пq3 ¦ ¦Лq2 ¦ ¦Пq3 ¦
+-----+------+------+------¦
¦ ^ ¦ ^Пq1 ¦ ^Пq1 ¦ ¦Нq2 ¦
+-----+------+------+------¦
¦ + ¦ ^Сq1 ¦ +Лq2 ¦ +Пq3 ¦
+--------------------------+
_1.5
Начальные условия: в поле зрения установлена самая левая па- лочка и машина настроена в состоянии q1.
Обозреваемая палочка стирается, сдвиг вправо (в поле зрения установлена следующая палочка) и переход к состоянию q2.
- 15 -
_1.0
-----------------------------------------
¦ ^ ¦ ^ ¦ ^ ¦ ¦ ¦ ¦ ¦ + ¦ ¦ ¦ ¦ ¦ ¦ ¦ ^ ¦
-----------------------------------------
q1
-----------------------------------------
¦ ^ ¦ ^ ¦ ^ ¦ ¦ ¦ + ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ^ ¦
-----------------------------------------
q2
_1.5
Последующие такты, как видно из столбца q2, сводятся к сдвигам направо сквозь все палочки и знак плюс до тех пор, пока не будет достигнута первая пустая ячейка:
_1.0
-----------------------------------------
¦ ^ ¦ ^ ¦ ^ ¦ ¦ ¦ + ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ^ ¦
-----------------------------------------
q3
_1.5
В эту пустую ячейку вписывается палочка и машина переходит в состояние q3:
_1.0
-----------------------------------------
¦ ^ ¦ ^ ¦ ^ ¦ ¦ ¦ + ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦
-----------------------------------------
q3
_1.5
При состоянии q2 происходит сдвиг влево сквозь все палочки и знак плюс до первой пустой ячейки слева:
_1.0
-----------------------------------------
¦ ^ ¦ ^ ¦ ^ ¦ ¦ ¦ + ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ^ ¦
-----------------------------------------
q2
_1.5
Тогда (входная пара ¦ q2) происходит сдвиг вправо, в поле зре- ния устанавливается первая из оставшихся палочек левее знака плюс:
_1.0
-----------------------------------------
¦ ^ ¦ ^ ¦ ^ ¦ ¦ ¦ + ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ^ ¦
-----------------------------------------
q1
_1.5
Машина переходит в состояние q1.
_1.0
-----------------------------------------
¦ ^ ¦ ^ ¦ ^ ¦ + ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ^ ¦ ^ ¦
-----------------------------------------
q1
_1.5
В результате этого цикла одна палочка левого слагаемого оказа- лась перенесенной в правое слагаемое. Если левее знака плюс было первоначально k палочек, то через k циклов все будут перенесены
- 16 - правее знака плюс. При (k+1)-м заходе вправо, в поле зрения маши- ны при состоянии q1, попадает уже не палочка (их нет уже левее знака плюс), а сам знак плюс. Тогда плюс вычеркивается и машина останавливается. Вместе с тем получена и нужная сумма.
_1.0
-----------------------------------------
¦ ¦ ^ ¦ ^ ¦ ^ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ¦ ^ ¦
-----------------------------------------
_1.5
_23.4. Алгоритмы повторного суммирования и умножения.
Пусть на ленту подается пара чисел М=2 и N=3 в унарной записи.
Например, М записано двумя палочками, а N записано тремя палочка- ми. Покажем изображение ленты в первоначальный момент подачи чи- сел.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.