Программирование машины Тьюринга, страница 9

_1.0 

----------------------------------------- 

¦ ^ ¦ ^ ¦ ^ ¦ ¦ ¦ ¦ ¦ + ¦ ¦ ¦ ¦ ¦ ¦ ¦ ^ ¦ 

----------------------------------------- 

_1.5 

Нужно чтобы при первоначальной подаче на ленту пары чисел M  и 

N, Машина  впала  бы в бесконечный процесс,  заключающийся в том,  что левое число M прибавляется к правому и потом оно прибавляется  к полученной сумме M+N,  потом к сумме M+2N и т.д. Для этого нуж-  но,  очевидно,  чтобы левое слагаемое не исчезло бесследно  после  первого сложения,  а, наоборот, чтобы его можно было бы восстано-  вить после каждого сложения и снова прибавить к числу, изображен-  ному правее знака плюс.  Этого можно добиться,  например, тем что  палочки левого набора временно не стираются, а временно заменяют-  ся какими то знаками или пометками. 

_3Функциональная схема: (роль пометки играет символ *) 

_1.0 

+---------------------------------+ 

¦     ¦  q1  ¦  q2  ¦  q3  ¦  q4  ¦ 

¦-----+------+------+------+------¦ 

¦  ¦  ¦ *Пq3 ¦ ¦Лq2 ¦ ¦Пq3 ¦      ¦ 

+-----+------+------+------+------¦ 

¦  ^  ¦ ^Пq1 ¦ ^Пq1 ¦ ^Нq2 ¦ ^Нq1 ¦ 

+-----+------+------+------+------¦ 

¦  +  ¦ +Нq4 ¦ +Лq2 ¦ +Пq3 ¦ +Лq4 ¦ 

+-----+------+------+------+------¦ 

¦  *  ¦ *Пq1 ¦ *Пq1 ¦ ¦Нq2 ¦ ¦Лq4 ¦ 

+---------------------------------+ 

_1.5 

Надо отметить,  что в этой функциональной схеме нет остановки,  поэтому процесс, описываемый в ней, не имеет конца. Соответствую-  щая машина реализует как раз  неограниченное  прибавление  числа,  изображенного левее знака плюс, к числу, изображенному правее ее. 

- 17 - 

Если правее знака плюс к началу работы нет палочек ( т.е.  второе  число 0 ), то правее плюса появятся M палочек, потом 2M, потом 3M  и т.д. без конца. 

_23.5. Алгоритм Евклида (нахождение НОД двух чисел). 

Этот процесс складывается из чередующихся  попеременно  циклов  сравнения и циклов вычитания. 

_3Функциональная схема: 

_1.0 

+----------------------------------------+ 

¦     ¦  q1  ¦  q2  ¦  q3  ¦  q4  ¦  q5  ¦ 

¦-----+------+------+------+------+------¦ 

¦  ¦  ¦ ¦Пq4 ¦ ¦Лq3 ¦ ¦Пq1 ¦ ¦Лq4 ¦ ¦Нq5 ¦ 

+-----+------+------+------+------+------¦ 

¦  *  ¦ #Нq2 ¦ $Нq1 ¦ *Пq1 ¦ *Лq1 ¦ *Нq5 ¦ 

+-----+------+------+------+------+------¦ 

¦  #  ¦ #Лq1 ¦ #Пq2 ¦ *Лq3 ¦ ¦Пq4 ¦ #Нq5 ¦ 

+-----+------+------+------+------+------¦ 

¦  $  ¦ $Лq1 ¦ $Пq2 ¦ ¦Лq3 ¦ *Пq4 ¦ $Нq5 ¦ 

+----------------------------------------+ 

_1.5 

Натуральные числа будут изображаться соответствующими наборами  палочек. Условимся наборы палочек, изображающие два числа, распо-  лагать на ленте один за другим без пропусков и не отделяя их спе-  циальным знаком,  причем в начале процесса в поле  зрения  машины  установлена самая правая палочка в наборе первого числа. Отметим,  что символы # и $ будут играть роль временных пометок. 

Разбор примеров создает впечатление о процессе, происходящем в  тьюринговой  машине,  как  о  чрезвычайной замедленной киносъемке  процесса вычисления. 

_2ДЕМОНСТРАЦИОННЫЕ ПРИМЕРЫ 

___2Пример_1. 

Составить функциональную  схему для машины Тьюринга,  осущест-  вляющую алгоритм замены символа '@' на символ '$'. 

___2Решение. 

Лента машины заполнена следующим  образом:  в  первой  и  n-ой  ячейках  располагается  пустой  символ '^',  а со второй по (n-1)  ячейку - символ '@'. 

. 

- 18 - 

Функциональная схема: 

_1.0 

+-------------------+ 

¦     ¦     q0      ¦ 

+-----+-------------¦ 

¦  @  ¦ $ Вправо q0 ¦ 

+-----¦-------------¦ 

¦  ^  ¦ ^ Стоп   q0 ¦ 

+-------------------+ 

_1.5 

Начальное состояние машины Тьюринга: @ q0 

Каретка указывает на ячейку: 2 

Состояние ленты перед выполнением программы: 

_1.0 

_40   1   2   3   4   5   6   7 

--------------------------------- 

¦   ¦ ^ ¦ @ ¦ @ ¦ @ ¦ @ ¦ ^ ¦   ¦ 

---------------------------------