Математическая логика. Шапорев С.Д (1019113), страница 53
Текст из файла (страница 53)
Таким обрюом, вместо формул г(х„хы...,х„,О)= б(х„х„..„х„) функция ) у(х„хз,...,х„,у+1)=Ь(х„х„...,х„,у,у (х,,х„...,х„,у)) получается из б, б,), г, с,О, Х и 1„ подстановкой, рекурсией »у(хО)= О(х), »у(х,ус!) = Ф(»у(х,у)) и рекурсией Р(хО)= х, г(х, у + 1) = Ф(г (х, у)), где»у (х, у) = г (О(х) у), О(х) = ту(х 0) = с" и (са, (х) сь, (х) ...с„„(х)0, б(ск, (х) а„(х),...,с, (х))). 54.9. а) функция у (х) получается из функции б(х) а помощью итерации у'(0) = О, у(х)=!б(х), если [ По опредалению (1,хи О, вбпх = Рассмотрим левую чаать формулы (О, х = О.
! х !1 !х1 т[!ь~ — ! =вбил.Здесь !(х)=вбил, б(х) 1+~ — ~.раасчитаем !24~ ~2~ неаколько значений функции у(хая)» х=О, у(0)=вбпО=О, к=!, Г(0+1)=б(» (0))=1е[ — =!е0=1, 2 )а=2, у(1е1)=б(у(1))=1е ~=1ьО=! 2 Гвбп 1.1 Очевидно, что — ~ = 0 прн любом ф > О, т. е. формула (г! вбп х = ![1+ П справедлива; (2! ) б) г~х+!+[ — ~ — [-'1) =2х — 1. 2х — 1= ~ талы Рз т аале ити в ЗЯЗ !'хо!1 ~х ! 7(х)=2х — 1, З(х)=хч1е~ — — —, функции 7(х)=2т — ! 2 ! (2~ удовлетворяет условны 1(0)=0.
Вычислим несколько значений функции й(! (х)) З(У(О+1))=У(О)в!+~~ „~ Я~, ]= =От!е~ — ]!-! — !=От!+040=1, (2) 'Е2~ З(7'(!т!))=(2 1-1)т1ч~ ' =2+1-0=2 ° 2 — 1=3, З(т"(2+ !)) = (2 2 — !)+1+ ~ =4в2 †1 3 †1, З(у(341))=(2 3 — !)ч1е~ ] — ~ ]= =6+3 — 2= 2 4 — 1=7 ит, д. Очевидно, что исхаднав формула верна в) !(х + 1 + !з!4х ч ! ))= хз ч- х , у (х) = х ч- х, !'(0) = О, З(х)= х+1+ (чйхе1), 7 (к+1) = З(7 (х)) = (т + х)+1+ (з)4(х' ч х)ч1~. доказательеыо аналогично пунктам ра) и (6). 5.4.10. (1,х и О, а] збпх=[ Если з (х) можетбытьполучснаиз З(ь) (О,х =О.
у(о)= о, с помощью итерации, то '... Тотда зйпх = й(0), (7" (х+ !7= З(т (х)) действительно, х = 0 вйп х = вйпО = О, х = 1, вйп(Ое!)=ь(зйпО)=Уь(0)=От!=1, х = 2, вйп(1+1)= в(зйпО)= в(0)= 0+1=1 и т д. Ча жл. Огвемг шм'ил ун залил (1,х=О, б) у(х)=вйп(х)=~ ' ' или з п(х)=1 — х. (О,х>0 Так «ак Т (0) = або(0) = 1, то операция июрации не подходит.
Рассмсчрим несколько значений функции д(х), приведенных в табл. 10.1. таалигза тол Таким образом, можно нсгзользовкю функцию д(х), подобрав ес аргумент у твк, чтобы при у = О, д(0)= 1, а дпв всех остальных значений удолжнобыть О(у)=0.
Если, например, у = 2а 2зйп(х), то эта задача выполнена. Итак, зйп (х) = й(2 ь 2айп(х)); в) 1. (х,,х,,х„)=О (х ). В самом деле, у(0)=1„(х,,х„...,х„)=0, У(Ое1)фй(1 (х, х, ...,х ))-х„ Т(1с1)= д(1н(хилз,...,х„))=ха ит. д; г) Т(х)=ах+бусо. Так как функцив 1„(х„х,„,х„) сааза мажет быть получена с помощью операции нюрироаания из функции х(х) 1см.л. 1а1), используем ззу функцию в суперпозиции Очевидно, х= 1;(х,у), у =1,(х,у),тогда .с(*, Ьсс.
) °,. ° а(*, ) К*, ),. Фз, > вм Х(0)+...ед(0); д1 х =1(хе 20/х )ь1).Действительно, г(х)=х', м=* аз*1 Гл Ю Ге Лнл ллгоднпюл т(О)=О. /(Ое/)=!=Отез(сг/!т)41=1, 2 (1 е 1) = 4 = ! -г 2(т//т )+1 = 4, / (2 г 1) = 9 = 2 Е 2(т)от )!. 1 = 9 10.2. Ответы и решения практического занятия Ио 12 58 1 Исколный алфавит А =-)А.В С). р=з. Р(Л)= ВС, ! (ЛС).— -Н,(Л,Р(Л))=!~(Л,Р(Л))=Л Далеепоопредеяищищ Р(СВ)= Нт(С Р(С))= В (С)= СС, Р(СВА)= Н,(СВ, Р(СВ))= В, Найдем теперк нее прелсглпляюляие фуюглии. В(т)=с(С(Кх))= с(ВС)= 3 ре е2 р' =342 3=9. В (х) = 9 = сопя 6,(х,У)=г(Н,(КгЗКу))=г, гле г — номер буквы ллфянны А, Ьт(г,у)=с(вя(Кх,Ку))=с(В,(Кх))= рс(а)4з=з.т ! 3, 0,(х, у)= с(Н,(Кт,Ку)) = с(/я (Кх,Ку))= с(а) —.
х Итак, гярелстлелл~ощие функнии икяекгт ннд. Г(0)= 9, няи !'(Зхл!)=Ь,(т,!:(х))=0 (х,у),г' — -12,3 2 (0) = 9, / (Зл т 1) = А, (х, 2(х)) = г', Г (Зл е 2) = Ь, (х, 2 (х)) = Зх е 3, /(Зх+З)= Ля(х,) (х))=.г, гле ! — номер последней буквы ряссмщрнелемого слова л ялфпеиге Л . Определим несколкко номеров слое и тнляеннй предстяелмощпк ф»нклий. г = 1, Г (! ) = й, (О, / (0)) = !й (О 9) = О, . = о, ! = 2, г(2) = А (о, / (о)) — — А, (о 9)= з о + з = з, г = 3, /(3)= 6,(ОС/(0))= Ь,(0,9)=0, оасзь Д Озаазн, рвшаннн, унааании з =1, 1(4)=1зз(1,1(1))=»,(!,з)=1, х = 1, з = 2, У(5) = »~ (1, У(!)) = 1з~(! 1) = 3 1+ 3 = б, 1 = 3, У (Е) = » (1, 7 (!)) = » (1,1) = 1, 1=1, у(7)=»з(2,У(2))=»з(2,3)=1, х=2, 1=2, у(8)=1зз(2,7(2))=»з(23)=9, з = 3, ~(9) = »з (2 .У(2)) = 1зз (2 3) = 2 1=1, 1(10)=»,(з,у(з))=й,(з,о)=1, х=з, з=2, У(11)=»з(3,~(3))=1з,(3,0)=12, =з, р(12)=»,(з,у(з))=»,(зо)=з.
Г(Л)=ВС,а, с(Л)=0, В(0)=9; Г(С)=Н,(Л,Г(Л))=Л, с(Г (С)) = с(Л) = О, с (Г(Л)) = 9, », (О 9) = 0; Г(СВ)= На(С,Г(С))=СС, «(СС)=3+3 3=!2, с(С)=3, с(Г(С))=0, »,(30)=12; Г(СВА)= Н,(СВ,Г(СВ))= В, с(В)=2, с(СВ)= 2+3 3=11, с(А)=1, йн(1 1,1)= 1~ =2. ~н=з. в. рн аз ! н л 5.8 2. Здесь р =5. Г(Л !1 У) = У ' Г(ЛС,А,Е)= НЯЛ,Г(Л,А.Е) Е)= Вз(Л)= ЛЕ Г(СР, А Е)= Нз(СГ(С АЕ) АЕ)= НЯСЕА, Е)= ЕАС, В(х)= с(Н(КУ,Кх))= с(у) = с, й (х з у х)= с(о(Уу)=с(у)+ рой+ р с(о)= 25х'->5у+ х, »з (х з, у, х) = О, »,(х З,у,х)=с(аЕ)=5+ рс(о)=5ха5, »з (х, з, у, х) = с(УОо) = х а 5 у + 25 а', »з(к,з,У,х)=ВСР = 4 !+3 5-з2 25=69.
ввг Глава гп Тес на а г гмов Т(О, у,х)=8(с)= й ~(5х е 1, у, с) = 211 (х, 1, у. 2) = 25х б 5 у + х, 2(5х . 2,у,с)=бг(х,г,у,х)=0, Т(бх+3,у, )=Ьт(х,г,у, )= 5хц 5, Т(5х+ 4,у,в)= Ба(х,г,у,х)= а +5у+ 2521, 2 (5х е 5, у, 2) = Ьт (Х, 1, у, 2) = бр. Г(С,А,Е)=Н,(Л,Е,А,Е)=Е. с(Е)=5, Ьт(0515) =5 От5=51 Г(С22, А, Е) = Н г (С, Е, А, Е) = ЕАС, с(ЕАС)м 3.1е! 51 5 25 =133, 2гц(3515)и 3е! 5425 5=!ЗЗ, — (1, = о, 5 8 3. ябпх = ' * наналвное слово 9,0! 110 или 9,00000 .
Програлгма (О, х и О, чашннм Тьюринга приведена в табл !О 2 Таблица гл.2 5.8 4. Проанализируем данну1о программу !таба. 10.3! по команлам лля сяов 9,010 и 4,100. Ьгйжн» уйу Часть я. Ответы, щения, указания Видно, что программа вычисляет функцию 1'1х)=хь1 Х~тя прн х и 0 конечное слово содержит Дх) вхождений символа 1, управляющая гшювка машины не находится в крайней левой позиции. 5.8.5 Здесь роль ненулевого символа аяфавита играет вертикальная ~ерточка.
Поставим програмиу (табл. 104), перерабатывающую исходное слово а (! ) п,. Тевлвип 14.4 58б Пусть ившина Зьюринга Т имеет алфавиты А=)аз,ап...,п„,), з,)=ф~е,д„...,д„) и Гзпппз,...,п,) —,т-местиаа словаРнаЯ фУнкция, заданная в алфавите А . Говорят, что машина Т правильно вычисляет функнию с[а,,пз,...,п,), если дп,а,аепз...п,п, ) — репер(анны...,а,)п .,и, для любой сисгсмы саов п„а„...,а, в алфавите А. Если жс г1п,,а„...,п,) не определено, то машина Т, начав работать в состоянии д,аеп,пвцз а„п,, нс должна никогда остановиться в состоянии де и не должна надстраи- вать ленту слева. для нашей функции Г1х)= хе у длл любою начального слова д,01'01' мапзина должна выдать результат и О! 'О.
Это можно слелать следующей системой команд (табл.10.5) при начальном слове, например, такого виде п,0110110. Гл в Гп. творю алгарнмюв Пгаляюг Газ 5.8 7. Введем понятия композиции машин Тьюринга Пусть заданы явс машины Тьюринга Т, и Тз, имшогпис обшнй внешний алфавит А = Уос,ап....а„) н внУтРсннис алфавиты Ягг = тф О„,д„) и яяз =~Во гды ., у, р Произвсдснисм машины Т, на машин> Т, навьи настоя машина Т, с том хгс внсшнин алфавитом, внутренним шфавнтом 4~з =(Ос,гб,...,О„,О„н,....гй„г) и спсдУюпгегд пРогРаммой пРогрямма первой машины Т, остасгся псизмснпой, .юлька символ пс замснястся на символ д„ч, в программе в~орогг»яшнпы Т, только сим- вол гус по мснястсн вссоспяльпгяссичволы д зямсняются па рм,ч, Совокупность всех команд маншп Т, н Т,. пзмспснных указанным способам, н будет программой машины Тз При составлсини программ для многих машин Тьарипга приходится использовать супсрпознпию функций.
Супсрпознпия модсвнрустсн произвсаснисм двух нли нескольких машин Тьюринга Дгя того чгооы было легче следить за работой ьшшин н таких слу чаях, введем слсдуюшие обозначения. Пусть П вЂ” программ* «акой-то машины с алфавитами А =тбй) и 9=(уя,дн...,гф), а Š— положительное игпУРальнос число. Если замсннгь в П символы д,,дз.....гф нв Чк гь Ф. Омши, ения, имамы б»»)»и ...,»(»,„.», а символ»)а на Чы„, то получим программу а тем же внешним шфавитом А = (0,1) и внугренним алфавитом )5 = (б»»)»»р,ф»,„). Э»у новую программу можно обозначить через П„. Если машина, начав работать в состоянии цб»!), переходит через некатоРое вРема в састоание п»Ч,„Оо то бУдеь» обозначать зтат пРоцесс шу»ОПкп»д,0».
Очевидно, что если П ),П ),...,П вЂ” программы некоторых машин Тьюринга в алфавите А =(О,!), то пеЩП, п,б»(5»П» п»Ч„,О»...П, п,б,О» Ф р) м эквивалентно пер»Оа (П (')П(') ...ПР )з»г),!), . Вернемся к решаемой задаче и рассмотрим сна»ала более простор случай: !з(х„хз)=хз, Исходное слово д,01ч01чО, необходимо полУ- чить конечное слово»1,01ч. Обратимся к примерам, разобранным в разделе 5.б, и обозначим программы аоответствующих машин Тьюринга: Б — левый сдвиг (примерЗ), Б' — правый сдвиг (пример с),  — транспазиция (пример5), 0 — вычиаление функции 0(х)=0 (пример 8), Ц=ВБ  — цикличеакий сдвиг (пример 7), Тогда для 1, (х„х,) =х, булем »» иметь д 01'О!" ~ )»О!'»)»01 (В),0!сб„О!ч(0)„О!чая»0...0ф ~дз»01-0 или сокращенно Б'ВОБ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
