В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 48
Текст из файла (страница 48)
Это обеспечивается командами: д,г -+ да! (для ! = О, 1, 2, ..., 9). Запишите все команды построенной машины Тьюринга в таблицу и примените ее к конкретным массивам палочек: 1, й, 9. 12.18, а. Используя программу счетчика, вычитающего единицу из десятичной записи натурального числа (задача 12.17), составьте программу машины Тьюринга, которая бы по десятичной записи числа и выписывала бы на ленту и палочек (шифратор). 12Л9. На ленте записаны два числа в двоичной системе счисления, разделенные звездочкой: 1011*101. Определите, какую операцию проделает с ними машина Тьюринга, начиная из стандартного положения (крайняя правая ячейка, состояние д,), если ее программа задается таблицей 12.20.
Вопрос, аналогичный вопросу из предыдущей задачи„ для ленты: 1101~1001 и для машины Тьюринга с программой: д,1 -+ д,ОЛ, 9,0 -+ д,Л, 9~1 -+ д,ОЛ, 9зО -+ 9зЛ* Чз1 -+ 94Л, д~е -+ -+ г)~Л, у~1 -+ д,ОЛ, д,ар -+ да. 12.21. На ленту подряд вписаны два конечных набора единиц, разделенные звездочкой. Составьте программу машины Тьюринга, которая выписывала бы подряд (без разделения звездочкой) столько единиц, сколько их в обоих наборах (сложение единиц). Указание. См. задачу 12.4. 12.22. На ленту подряд вписаны два конечных набора из т и л единиц, разделенные звездочкой.
Причем в левом наборе единиц не меньше, чем в правом (и > л). Составьте программу машины Тьюринга, которая в левом наборе оставляла бы ровно столько единиц, на сколько единиц в левом наборе больше, чем в правом, а все остальные единицы стирала бы (вычитание единиц). Р е ш е н и е. В задаче 12.5 рассматривалась машина Тьюринга, которая выполняла эту операцию для л < 2 и любого и > л. Если программу этой машины слегка модифицировать, то она будет решать данную задачу. Необходимо ввести еще одно дополнительное состояние д, и следующие команды, связанные с ним: д,а, -+ д,а,П, д, *-+ д4*П. Команду 9,1-+ 94аоП заменить на команду 4,1 — ~ д,ааП.
232 Применим новую машину к слову 111114111 и сравним ее работу на этом слове с работой на этом слове машины из задачи 12.5: 11111*11Ч11 1111141Ч21ао 11111Ч2411ао 1111Ч31*11ао ~ 1111аоЧ5*11ао ~ 1111ао*Ч411ао 1111а0*11Ч4ао =' 1111ао*1Ч11ао ~ ~ 1111аооЧ21аоао ~ 1111аоЧ2'1аоао ~ П11Чзао'1аоао ~ 111Ч21ао41аоао ~ 1 1 1 аОЧ5а04 1аоао 1 1 1 аоаОЧ5" 1аоао 1 1 1 аоаооЧ41 аоао О 04 Ч4аоао 1 аоаО*Ч|1аоао 111аоаОЧ24аоаоао ~ 111аоЧзао*аоаоао 111Ч2аоаооаоаоао =' 11421аоаооаоаоао 11аоЧ5аоао*аоаоао 11аоаоаоЧ54аоаоао 11аоаоаооЧ4аоаоао =' 11аоаоаоЧ54аоаоао ~ 11аоаоаоЧоаоаоаоао. Дополнительное состояние Ч5 предназначено для того, чтобы отличать положение машины между левым массивом единиц и звездочкой от ее положения правее звездочки.
Примените данную машину ко всем словам из задачи 12.5 и убедитесь, что машина выполняет требуемое вычитание. 12.23. Два конечных набора из т и и единиц записаны на ленту подряд. Машина в начальном положении обозревает крайнюю правую единицу левого набора. Постройте программу машины Тьюринга, которая выдавала бы набор единиц из НОД(т, и) штук, а остальные единицы стирала бы.
Ре ш е н и е. Проанализируем работу машины Тьюринга из задачи 12.6 и покажем, что она решает поставленную задачу, реализуя алгоритм Евклида для нахождения наибольшего общего делителя двух натуральных чисел л2 и и. Придадим алгоритму Евклида следующее алгоритмическое описание: 1) обозревайте два числа и и л, а затем переходите к следующему указанию; 2) сравните обозреваемые числа: «2 = и или «2 ( л, или 2л > л и переходите к следующему указанию; 3) если и = и, то л2 — искомый результат и процесс вычисления следует остановить; если и ~ л, то переходите к следующему указанию; 4) если первое обозреваемое число меньше второго, переставьте их местами и продолжайте обозревать, переходите к следующему указанию; 5) вычитайте второе из обозреваемых чисел из первого и обозревайте два числа: вычитаемое и разность, а затем переходите к указанию 2.
Описание работы данной машины Тьюринга будем сопровождать иллюстрацией применительно к случаю и = 4, л = 6 (задача 12.6, в). Начальная конфигурация имеет вид: 111Ч,1111111. Программа состоит из чередующихся циклов сравнения (в них участвуют лишь состояния Ч„Ч,) и циклов вычитания (в них участвуют лишь состояния Ч„Ч4). Буквы а и р внешнего алфавита будут играть роль неких пометок, которые будут делаться для запо- 233 минания тех или иных обстоятельств, возникающих в процессе работы.
На первом цикле сравнения машина помечает (заменяет) последовательно единицы левого числа и буквами а, а единицы правого числа и буквами )3. При этом машина'ставит одну а, идет вправо и ставит одну К возвращается влево, ставит а, снова идет вправо, ставит 13, и т.д.
Через 37 шагов создается следующая конфигурация: ааааЩЗД4411. Затем в состоянии д, головка машины устремится влево, пройдет массивы Д и а и досппнет пустой ячейки (45-й шаг): д,ааааааЩ3ф11. Первый цикл сравнения завершен. В результате него машина обозревает пустую ячейку в состоянии д, и для нее это означает, что и ( и. Теперь начинается цикл вычитания. В состоянии д, головкадвижется вправо, стирая все подряд буквы а (заменяя их на аа) и заменяя все р на 1, пока не обнаружит первую единицу (54-й шаг): ааааааа,а,11119411.
Затем головка передвинется на одну ячейку влево„и машина перейдет в состояние д, (55-й шаг): а0ааа,а,а,1114~111. Первый цикл вычитания завершен. В результате него машина оказалась в начальном состоянии, но уже для чисел и, = т = 4 и л, = л — т = 2, т.е. вычисление НОД(4, 6) сводится к вычислению НОД(4, 2): НОД(4, б) = НОД(4, 2). Далее оба цикла прокручиваются второй раз. На втором цикле сравнения машина пометит (заменит) буквами а три единицы левого числа и, пометит (заменит) буквами ~3 две единицы правого числа л — гл и в состоянии д, выйдет на правую пустую ячейку (75-й шаг): ааа0а0а0а01аааЩ3д~аа. Второй цикл завершен.
В результате него машина обозревает пустую ячейку в состоянии дь и для нее это означает, что т > и — ль Теперь начинается второй цикл вычитания. В состоянии д~ головка движется влево, стирая все подряд буквы Д (заменяя их на аа) и заменяя все а на 1, пока не обнаружит первую единицу (81-й шаг): ааа0ааа,аале,1111а0а,а0. Затем головка передвинется на одну ячейку вправо и машина перейдет в состояние д, (82-й шаг): аааааааааа14~111а0аааа.
Второй цикл вычитания завершен. В результате него машина оказалась в начальном состоянии, но уже для чисел т~ = т, — и, = 2 и и, = и, = 2, т.е. вычисление НОД(4, 2) сведено к вычислению НОД(2, 2): НОД(4, 2) = НОД(2, 2). Этот процесс повторения циклов сравнения и вычитания происходит до тех пор, пока задача не будет сведена к случаю двух равных между собой чисел (в нашем примере это уже достигнуто). Тогда начинается заключительный цикл сравнения, который должен привести к результативному завершению процесса. После замены двух левых единиц буквами а и двух правых единиц буквами р третий цикл сравнения завершается следукяцей конфигурацией (97-й шаг): а,ааа0а0аад4ааЩ)ц~а0аа.
Наконец, головка машины, находящейся в состоянии (4, движется вправо, стирая подряд все а (заменяя их на 234 а«) и заменяя все О на 1. В этом же состоянии д« машина выходит на пустую ячейку (100-й шаг): ааааа»а»а«а»а»11д«а»а«а«. Для нее это означает, что т2 = п2 и оставшееся число единиц (и,) и есть искомый результат. После этого машина выполняет заключительный шаг (101-й шаг): а»а»а»аоаааоао1до1а,а,а». Восстановите все пропущенные шаги в работе машины. 12.24. Постройте машину Тьюринга, осуществляющую перевод слова 001"10 в слово 01"00, где 1" = 1...1 (х единиц). Причем в начальном положении машина должна находиться в состоянии д, и обозревать правую ячейку, эту же ячейку она должна обозревать и в момент остановки.
(Эта машина называется «перепое пуля» и обозначается А.) Р е ш е н и е. Приводим программу машины. Рядом с командами изображаем конфигурации, получающиеся в результате выполнения соответствующих команд: Начальное положение д 0 -+ д П дО-+ д,1 дз дз дз дл д«1 -«д,О д,О -+ д,Л дг1 -» д6Л д,Π— д О до Проанализируйте работу машины.
12.25. Постройте машину Тьюринга, перерабатывающую слово 01" (в слове х единиц) в это же слово 0 1"0 из стандартного начального положения, причем в момент остановки должна обозреваться крайняя левая ячейка. (Эта машина называется «левый сдвиг» и обозначается Б .) 235 12.26. Условие аналогично условию предыдущей задачи, но в начальном положении должна обозреваться крайняя левая ячейка, а конечное положение стандартно. (Эта машина называется «правый сдвиг» и обозначается Б'.) У к а з а н и е. Программа этой машины получается из программы машины Б заменой символа Л символом П. 12.27. Постройте машину Тьюринга (называемую «транспозиция» и обозначаемую В), которая перерабатывает слово 01"01'0 в слово 01»01"О, причем в начальном и конечном положении обозревается ячейка, содержащая О, между двумя наборами единиц. 12.28.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
