В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 61
Текст из файла (страница 61)
6. а) 1; б) 1; в) 11; г) 11; д) 111. 8. Прокомментируем идею работы алгоритма применительно к слову 11111. Алгоритм имеет прямой ход и обратный ход. На прямом ходе происходит разбиение данной совокупности единиц на тройки и выяснение того, сколько единиц останется на ленте (О, 1 или 2) после выделения максимально возможного целого числа троек. Прямой ход осуществляется с помощью трех состояний д„ дз, дз. Головка движется справа налево вдоль ряда единиц, последовательно переходя в состояния д„д„д„затем снова в дь д„д, и т.д., но до тех пор, пока не появится первая пустая ячейка ао. Ясно, что если она появится в состоянии д~ (так было в только что рассмотренной последовательности конфигураций по переработке слова 111), то на ленте было число единиц, кратное трем, и искомый остаток равен нулю.
Если пустая ячейка появится в состоянии д„ то искомый остаток будет равен 1. Наконец при состоянии ?, остаток равен 2. Последняя ситуация имеет место в нашем случае. От слова ао1111д,1а, (1-й шаг) мы приходим к слову (6-й шаг) дзао11111ао. Теперь начинается обратный ход. Мы должны вернуться на правый конец данного слова, стерев все записанные единицы. Достигнув первой пустой ячейки справа, нужно записать соответствующее количество единиц: О, 1 или 2. Для этого через весь обратный ход должна быть пронесена информация о том, сколько же единиц должно быть записано в результате, т.е.
должна быль пронесена информация о том, в каком состоянии машина вышла на первую пустую ячейку слева. Для сохранения информации о состо- 294 янин дг (1 = 1, 2, 3) в процессе обратного хода предназначены два состояния д; и д;„. В рассматриваемом случае должна быть сохранена информация о состоянии д,. Головка делает один шаг вправо, и машина переходит в состояние аг (7-й шаг): аоаг11111ао. Цикл по стиранию одной единицы выглядит так: 8) аоаоао1111; 9) аоао9г1111. Далее, таким же образом стираются оставшиеся четыре единицы и на 17-м шаге в состоянии г)г головка обнаруживает пеРвУю пРавУЮ пУстУю ЯчейкУ: аоаоаоаоаоаог7гао. Наконец, с помощью состояния щг на ленту заносятся две единицы (20-й шаг): аоаоаоаоаоао11доао.
Подумайте, можно ли обеспечить запоминание на обратном ходе состояния г7г только с помощью одного состояния д;, без использования состояния д;,г. 9. Йз программы видно, что головка всегда движется только вправо и при этом содержимое ячеек не меняется. Если перерабатываемое слово содержит один массив единиц, записанных без пробела, то, пройдя его в состоянии дь машина на первой же пустей ячейке перейдет в состояние дг и, находясь в нем, будет вечно двигаться вправо (см. задачу 10.9, в). Если при этом она встретит на своем пути еще один массив единиц, то она на первой же единице этого массива перейдет в состояние д„пройдет этот массив и, достигнув в состоянии дг первой пустой ячейки, остановится (см.
задачу 10.9, а). Дальнейший характер перерабатываемого слова не важен (см. например, задачу 10.9, б) — машина остановилась; г) 1аоаоаоао1доао; д) 11аоао119оао, е) не остановится; ж) 1ао1доаоао1ао1; з) не остановится; и) ао1доаоао1; к) 11ао1 жоао. 10. а) Машина останавливается„вьщав слово 1ао1аоао1, обозревая в состоянии дг четвертую ячейку слева; б) машина останавливается, выдав слово 1ао!ао1 и обозревая в состоянии аг вторую левую пустую ячейку от полученного слова; в) машина не меняет данного слова и останавливается в состоянии дг, обозревая вторую левую пустую ячейку от этого слова.
11. а) Машина выдает слово 1а,а,а,1ао1 и останавливается в состоянии д„обозревая третью ячейку справа; б) машина выдает слово 1а,ао1 и останавливается; в) машина не меняет данного слова; перед остановкой обозревает в состоянии дг самую левую ячейку с буквой данного слова. %1 + Чг1Л йг1-+ Яг(Л Чгао -+ 9гаоП 9г1 -+ Чо). 13. г7,1 -+ агаоЛ, аг1 -+ агаоЛ, агао -+ аоао. ДРУгой ваРиант: а,1 -+ -+ ФаоЛ Фао -+ г7оао. 15. Программа, реализующая идею из указания д,1 -+ дгоЛ, 9г1 -+ Л, дг * -+ Л, 9гао -+ цгаоП, г7га -+ дгаП, дг1 -+ доаП, 941 -+ П, 94 о -+ П, жоао -о ФаоП, 94а -+ Ч~аЛ, Ч~ о -+ Чо*Л, г7оа — > Чо1Л, Чо1 -+ -+ Л, жоао -+ г)оП, Чо1 -+ П, г7о о -+ П Чоа -+ ЯоаоП Чово -+ Чо 9г * -+ -+ 9гП Чг( -о П, дга -о дг1П, дгао -+ доаоЛ, до1 -о Л, доо -+ Л, Чоп -+ 9оаоЛ, Чово -+ Чо 295 17.
Внешний алфавит: (1, 2, 3, 4, 5, 6, 7, 8, 9), два состояния: Чо (остановка), Ч, (рабочее состояние), функциональная схема: Чг! -+ Чо(! — 1) (для ! = 1, 2, ..., 9), Ч,О -+ Чг9Л. 19. Выпишите самостоятельно всю последовательность конфигураций, возникающих в процессе работы. Заключительная конфигурация имеет вид Чо10000*000. Если в двоичной системе счисления произвести сложение двоичных чисел 1011 и 101, то получится 10000. Таким образом, машина произвела сложение данных двоичных чисел. Данный алгоритм выполняет следующие действия. Каждую букву из двух данных слов, разделенных звездочкой, кроме самой звездочки, он заменяет на букву 0 (обнуляет слова), а затем в первой пустой ячейке слева от левого слова вписывает букву 1.
В частности, 1б1 => 10, 1*11 => 10б00, 11*11 ~ 100бОО, 11*1 => 100*0, 10*1 ~ 100*0, 1001*111 => 10000*000, 1101б11 => 10000б000. Это означает, что данный алгоритм не является алгоритмом сложения двух произвольных чисел, записанных в двоичной системе счисления. И только для некоторых таких чисел его результат представляет собой сумму исходных двоичных чисел, как это произошло и с данными числами. (Найдиге в только что указанных соответствиях ситуацию, когда результат действия данного алгоритма совпадает с суммой исходных двоичных чисел, и придумайте другие пары двоичных чисел, обладающие таким свойством.) 20. Машина Тьюринга выполняет вычитание для двух данных двоичных чисел: 1101б1001 => 0100*0000, но не представляет алгоритма для вычитания любых двух двоичных чисел в двоичной системе счисления.
25. ЧгО -+ ЧгОЛ, Чг1 -+ Чг1Л> ЧгΠ— ! ЕгО. 27. ЧгО -+ ЧгОП, Чг1 -+ Чг1П, ЧгО -б ЧзО> ЧзО -+ ЧбОЛ> Ч41 -+ ЧзО, ЧзО -+ ЧбОЛ, Чб1 -+ Чб1Л, ЧбО -+ Чг1, Ч40 -+ ЧгО, Чг1 -+ Чв1Л, Чв1 -+ -+ ЧоО> ЧзО -+ ЧгоОП> Чго1 -з Чго1П, ЧгоО-+ Чц1, Чц1 -+ Чп1Л, Чп1 -+ + ЧгзО, ЧцО -+ Чг40Л> Чгб1 -+ Ч!41Л> ЧмО -+ Чм1> ЧгО + Ч!61> Ч!61 + + Чг71Л> Чгг1 -+ Ч,зО Чгз1 -+ Чг1> Ч!50 -+ ЧгО> ЧвО -+ ЧгвОП> Чгв1 + Чгв1П> Ч!вО + Ч!О> ЧпО -+ ЧгоОП> Ч!о1 -+ ЧоО.
28. ЧгО -+ ЧгП> Чг1 -+ ЧгП, ЧгО -з ЧзЛ, Чз1 -+ Ч40> Ч40 -+ ЧзП, ЧзО + Чб1 Чб1 "+ ЧбП, ЧбО -+ ЧгП> Чг1 + ЧгП> ЧгО + Чв1> Чв + ЧвЛ ЧвО -+ ЧоЛ> Чо1 -+ ЧоЛ> ЧоО -+ ЧгО. 32. а) Ч,О -+ ЧгП, Чг1 -+ Чг1П, ЧгО -+ Чз), Чз1 -+ Чз1Л, ЧзО -+ ЧоО; б) ЧгО -+ ЧгОП, Чг1 -+ Чг1П, ЧгО -+ ЧзОЛ, Чз1 -+ Ч40> Ч40 -+ ЧзОЛ, ЧзО -+ Ч,О. 33. а) Б'ВОБ . 34. б) ЧгО -+ ЧгОП, ЧгО -+ ЧзОЛ, Чг1 -+ Чг1П, Чз1 -+ Ч40> ЧбО -+ -+ ЧзОЛ> ЧзО -+ ЧоО (для х = 0), Чз1 -+ Чз1Л, ЧзО -+ ЧоО; г) из стандартного начального положения вычисляется машиной: Ч,О -+ Ч,1, Ч,1 -+ Ч,ОЛ, Ч,1 -+ Ч,ОЛ, Ч,Π— з Ч,О.
Составьте программу, правильно вычисляющую данную функцию; 29б д) программа машины Тьюринга, вычисляющей функцию из стандартного начального положения: Ч,1 -+ Ч,аоЛ, Чг1 — «Чг1Л, й'-+ Чг*Л, йао -+ йаоП, й1 -«Ч«аоП, Ч41 -+ Ч41П, Ч4« -+ Чо«П, Ч«ао -+ йаоЛ й1 -+ й1 й* -+ Ы*Л (й'го -+ ЧгаоП й* -+ Чоао) (Чо1 -+ Чо)Л Ч«1 -+ Чз(Л Чзао -+ ЧоаоП Ч«1 -+ ЧоаоП й* -+ Чо1) (Чз* -+ ФоаоП, йо1 -+ ФоаоП йоао -«Чоао). Алгоритм работы данной программы состоит в следующем. На ленте записаны подряд два массива единиц (по х и у штук соответственно), разделенные звездочкой «. Начиная из стандартного начального положения (крайняя правая единица массива у), машина стирает крайнюю правую единицу и движется влево, минуя звездочку, к крайней левой единице. Стирает ее и возвращается на правый край. Стирает единицу, движется на левый край. Стирает там одну единицу и возвращается на правый край и т.д.
Если на некотором цикле единицы справа иссякнут, а слева они еще будут иметься (т.е. х > у), то на первую правую единицу левого массива х машина выйдет в состоянии Чо. Начнет работать группа команд, заключенных во вторые круглые скобки в записанной выше программе, и машина выдаст результат 1.
Если же на некотором цикле иссякнут единицы левого массива, а в правом массиве они еще будут иметься (т.е. х ( у), то сигналом к этому для машины послужит ее выход на обратном ходе на ячейку со звездочкой «в состоянии Ч,. В этом случае начнет работать группа команд, заключенных в третьи круглые скобки, и машина отработает результат О.
Наконец, если на каком-то цикле при обратном ходе окажется, что иссякли как единицы правого массива, так и левого (т.е. х = у), то сигналом к этому для машины послужит ее выход при следующем прямом ходе на первую слева пустую ячейку в состоянии Чо. Начнет работать группа команд, заключенная в первые круглые скобки, и машина вьщаст результат О, заменив на него звездочку; з) машина Тьюринга с внешним алфавитом А = (ао, 1, а, 11), алфавитом внУтРенних состоЯний Д = (Чо, Чь Ч„..., Ч,) и пРогРаммой (начинающей работать из стандартного начального положе- ниЯ): йао -+ йао й1 -+ ЧгРЛ йао -«ЧзаоП> Чг1 -+ й1Л, Чзао-+ -+ Чгаоп й1-+ Ч«РП Чзо«-«Чзо«П ЧзР-«ЧзаоП Чоао-+ Чзс«П Ч41-+ -+ й)П Ч4« -+ Чос«П Ч4Р -+ Ч«РП Чгао -+ ЧоаоЛ Чгао -+ ЧзаоП й1 -+ -+ Ч«1Л Чоа -«ЧооЛ, Чоб -+ Чо(1Л, Ч,ао -+ йаоП, Чга -+ Чг1Л; к) машина Тьюринга с внешним алфавитом А = (ао, 1, а, Щ, алфавитом внУтРенних состоЯний Д = (Чо, Чь Ч„Ч,, Ч4) и пРогРаммой (начинающей работать из стандартного начального положе- ниЯ): Ч~ао -+ Ч«аоП, Ч,1 -+ ЧгДЛ, Чга -+ йаЛ, Чгао -+ Чзг«П, й1-+ «Чг)Л Чгс«+ ЧгоЛ Чз) + Чз1П йп + Чз««П Чз«+ Чг«'Л Ч«ао + Чо( Ч«а -+ Ч,1П, Ч40 -+ Ч«1П.
36. Ях) = х+ 2. 37. Ях, у) = х. 297 1. б) <р(х) = Я(Я(...Я(х))...) (функция о применена и раз); в) <р(х, у) получается примитивной рекурсией из Ях) = 1',(х) и я(х, у, г) = 5(1,'(х, у, ~)); г) ср(х, у) получается примитивной рекурсией из р(х) = 0(х) и я(х, у, х) = 11(х, у, ~) + 1',(х, у, ~). 3. б) <р(х, 0) = 1, ср(х, у+ 1) = х <р(х, у); в) вя(0) = О, вя(х+ 1) = = 1 = о(0(х)); г) вя(0) = 1, вя(х+ 1) = 0 = 0(х); д) 0 — 1 = О, (х+ + 1) — 1 = х; е) х — 0 = х, х — (у+ 1) = (х — у) —. 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
