1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 58
Текст из файла (страница 58)
Издоказанного вытекает предложение 7.5.11.DПусть, как и выше, R.o и R1 неотделимые непересекающиеся :Е-подмножества w. Обозначим через Ф(хо) и Ф(хо) :Е-формулычит выбору парыИтак,(4)(ko, lo),так какдоказано, и hп есть изоморфизмсигнатуры а0 такие, чтоR.o =-,!"Ф[хо] иR,-,!"=Ф[хо]. Определимследующие последовательности :Е-формул:Фо(хо)=. Ф(хо),=. 3хп(S(хп+1, Хп) /\ Ф(хп)),-:-0фп =. Фп(О) = (Фп)~n, п Е r.,J,Фо(хо) =. Ф(хо),Фп+1(Хп+1) =.
3хп(S(хп+1,Хп) /\ Фп(Хп)),-=-°\J!n =. Фп(О) = (Фп)~п, п Е w,-7Г-:-0~8n =. А, ---+ (Фn---+ Фп), п Е !.,J.Фп+I (хп+I)Аналогом предложенияПредложение(а) Если п Е(т. е. 0п Е Та0 ).(б) Если п Е7.5.12.R.o,R 1,7.5.5являетсяСправедливы следующие утверждения.то предложението существует0nNЕтождественно истинноw такое, что если Q( -конечная алгебраическая система сигнатуры а0 такая, чтои IAI ~ N, то Q( F ~еп.Q(F Л7"294Гл.Вычислимость7.До к аз ат ель ст в о. Пусть п Е .Ro и Q1 произвольная алгебраическая система сигнатуры аа.
Если Q1 F ~А7", ТО Q1 FЕслиQ1 р л7° и система Q1 бесконечна, то существует подсистема Qto ~end Qt,en.изомо~ная..,,,..{)n1r. Легко проверить~то п Е .Ro влечет n1r р Фn. Но тогдар фn и Q1 рQtoдля некоторого0n. Если Q1 р А, и-:-ОЕ w. Тогда Q1 р ~ii,n·kсистема Q1 конечна, ТО Q1 ~-:-О-:-Оnk р -:-ОФn, n1r р Фn, И тогда nи п Е .Ro n R, = so. Пришли к противоречию.п Е .Ro, то 0n тождественно истинна.Q1 р фn влечетПусть п ЕТогдаR,.-:-Оn1r р Фn.-Следовательно, Q1 рЕ R1. ОднакоnЕ5.7.10~F-:-О.Roпринципа-:-О:Е-рефлексии существует N Е (J) такое, чтоN = Плтфп ·Тогда еслиN, то Плт изоморфна концевой подмоделиIAI ;):nkтак какТаким образом, еслиСогласно следствиюn1r r0n,Qt.---:-1ГСледовательно, Q1 р Фn.
Если Q1 р А 1 и система Q1 конечна, то Q1 ~ Пkдля некоторогоПk р ~...,,,..{)n1r р ~. п Е .Ro, но п Е R1, п Е .Ro n R 1 = so; противоречие.Следовательно, Q1и..,,,..{)k Е w, k ;;?: N и Q1 р ~Фn, так как Q1 р Фn влечетF ~en.DОсновным следствием предложения7.5.12Предложениебесконечное подмножество wKs'==;{П~17.5.13.п ЕS}.ПустьS -Тогда теорияявляетсяTh(Ks)классаKsявляетсянаследственно неразрешимой.До к аз ат ель ст в о аналогично доказательству предложения§ 7.6.ПерейдемкописаниюМашины ТьюрингаклассаА.
М. Тьюрингом и Э. Постом валгоритмов,иR.которыйбылвведен1936 r.Пусть заданы два конечных множества А иL7.5.6.DМножество четверок Р=Q,{(xi,Yi,ui,vi)не содержащих букв1i ~ m} называетсяпрограммой с внешним алфавитом А и с внутренним алфавитомесли Xi ЕQ, YiЕ А, ui ЕQ, viЕ АQ,m.U {L, R} и для любого i ~v) будем называть команВ дальнейшем элементы программы (х, у, и,дами и обозначать через ху-+Определение.Машинойuv.ТьюринганазываетсяQ, ао, qo, q1, Р), удовлетворяющая следующим условиям:1) множества А, Q конечны, не пересекаются и небукв L, R;2) ао Е А; qo, q, Е Q;шестерка(А,содержат§ 7.6.3)РМашины Тьюринга295такая программа с внешним алфавитом А и внутренним-алфавитомQ,чтоа) не существует двух различных четверок в Р, у которыхпервые и соответственно вторые члены совпадают,б}qoне является первым членом ни одной четверки из Р.Машинным словом с внешним алфавитом А и внутренним алфавитом(или просто машинным словом в (А,Qслово о: в алфавите Адля некоторого q ЕПусть о:-U Q,-1-в) слово Ьо:1, если с= а и Ьг) слово о:, если ЬПусть о: иU {q}слово в алфавите В и а ЕВ.
Слово ао:а будем обозначать= Ьо:1 с, где Ь, с Е В,о: 1 , если Ь = с = а;0:1 с, если Ь = а и с -1- а;а) словоназывается такоеи о: содержит ровно одно вхождение символа q.Qчерез о:а. Если о:б} словоQ))что о: является словом в алфавите А(3 --1-а и с-1-то через О:а будем обозначатьа;а.машинные слова в (А,и элемент q ЕQ)в о:. Будем говорить, что машина Тьюринга Мпереводит слово о: в слово(3м(обозначаем о:---+=(3),(А,Q входитQ, ао, qo, Q1, Р)если выполняютсяследующие три условия:1)2)3)если о:аоесли ааоесли о:ао= o:1qao:2 и qa---+ rb ЕР, Ь Е А, то (3 = (o:1rbo:2)a= o:1aqbo:2 и qb---+ rL ЕР, то (3 = (o:1rabo:2)a0 ;= o:1qao:2 и qa---+ rR ЕР, то (3 = (o:1aro:2)a0 •0;Отметим, что машина М может переводить слово о: только в однослово. Это следует из условияЕсли машинное слово о: в (А,М=(А,Q, ао, qo, qi, Р)3,Q)а) определения машины Тьюринга.не переводится машиной Тьюрингани в какое слово(3, то будем говорить, что о: 3, б) определениятупиковое слово для М.
Заметим, что из условиямашинысимволТьюрингаqo,следует,что если машинное слово о: содержитто оно является тупиковым для М.Пусть о:-машинное слово в алфавите В. Слово, полученное из о:заменой всех вхождений символа Ь на пустое слово, будем обозначатьчерез о:/Ь.Определение. Пусть М=Q, ао, qo, Qi, Р) - машина Тьюринга\ { ао}. Будем говорить, что машинаМ преобразует слово о: в слово (3 (обозначаем М(о:) = (3), еслисуществует последовательность ')'о, ...
, 'Уп машинных слов в (А, Q),и о:, (3 -(А,слова в алфавите Аудовлетворяющих следующим условиям:1) ')'О= q10:;2) (3 = ('Уп/qо)/ао;3),'i~ 'Yi+l, i < п.296Гл.Вычислимость7.Заметим, что если для последовательности ,о,условияl)-3),в алфавите А\то словосодержит вхождение'Yn... , 'Упвыполнены/3 -так какqo,слово{ао}.Ясно, что машина М может преобразовывать слово а только в однослово.
Если машина М не преобразовывает слово а ни в какое слово,то будем говорить, что машина М не применима к слову а или чтозначение М(а) не определено. В этом случае или существует бесконечная последовательность ,о,iЕ,о,w,... ,'Уп,".. .,для которои ,о= qi аим'Yi ---.'Yi+ 1,или существует конечная последовательность машинных слов... , 'Уп,удовлетворяющая условиямне содержащееl)иа 'Уп3),- тупиковое слово,qo.Определение. Частичная функцияf:Х---. w,Х <:;:;wn,называетсявычислимой по Тьюрингу, если существует машина Тьюринга М=(А,Q, ао, qo, q1 , Р), для которойа) О, l Е А, ао # О, ао # l;=выполняются условия:б} машина М применима к записи n-ки а ~ а Е Х;в) М(а) = е для а Е Х иf(a) =е.Такую машину М будем называть машиной Тьюринга, вычисляющейфункциюf.Очевидно, что все вычислимые по Тьюрингу частичные функциивычислимы.Пример7.6.1. Построим машину Тьюринга М, вычисляющую= 2n.
Пусть М = (А, Q, а, qo, qi, Р), где А= {О, l, а},{qo, q1, q2, qз, q4}, а Р состоит из следующих четверок:функциюQ=f(n)---.qзR,qз l---. q20,q20 ---. q2L,q2a ---.qзО,qза---. q4L,q40---. q4l,q4l ---. q4L,q1 l ---.qзО,qзОq4a---. qoa.Предоставляем читателю самому убедиться, что эта машина действительно вычисляет функциюмq1 l l l ---.мм---. q2aOOl---.мм= 2n.f (2):f(n)ты выпишем <<процесс вычисления>>qзOOl---.
OqзlмДля иллюстрации ее рабоммl---. Oq20l---. q200I---.ммммqзOOOl---. OqзOOl---. OOqзOl---. OOOqзl---.ммммм---. OOOq20 ---. OOq200 ---. Oq2000 ---. q20000 ---. q2aOOOO ---.~ qзООООО ~ ОqзОООО ~ ООqзООО ~ ОООqзОО ~~ ООООqзО ~ ОООООqз ~ OOOOq40 ~ OOOOq4 l ~ммммм---. OOOq40l ---. OOOq4 l l ---.
OOq40l l ---. OOq4 l l l ---.§ 7. 7.Рекурсивные функции297Имеет место следующаяТеоремаКласс частичных функций, вычислимых по Тью7 .6.2.рингу, совпадает с классом частичных Е-функций.Доказательствотого,чтовычислимыепоТьюрингучастичныефункции являются частичными Е-функциями, мы предоставляем читателю в качестве упражнения. Доказательство другой части теоремыдовольно громоздкое и состоит по существу из выписывания большогоколичества программ, поэтому мы его опускаем.В силу теоремы7.6.2имеет место следующий тезис, являющийсяосновным принципиальным положением об <,универсальности,> вычислимости на машинах Тьюринга: любая вычислимая частичная функция вычислима по Тьюрингу (тезис Тьюринга).§ 7.
7.Рекурсивные функцииВ настоящем параграфе мы приведем еще один способ уточненияпонятия вычислимой функции, который можно назвать алгебраическим,так как определяемый класс функций будет порождаться изнекоторых простейших функций с помощью некоторых операций.Пусть Фп= UФп--семейство всех n-местных частичных функций, а ФnEwОпределим на семействеS, R, М,Ф всех частичных функций операторыкоторые сохраняют вычислимость функций.Пусть п, k Е u.1, /. . . , 9п -=семейство всех частичных функций.-(п+1)-местная частичная функция, go, ...k-местные частичные функции. Определим k-местную ча-стичную функциюh(m1, ... , mk) не определено,90, ...
, 9n не определенана (m1, ... ,mk), и если все 9О,···,9п определены на (m1, ... ,mk), тоh(m1, ... ,mk) = f(9o(m1, ... ,mk), ... ,9п(m1, ... ,mk)). Будем говорить,что h получена регулярной суперпозицией из f, 90, ... , 9п и обозначатьэто следующим образом: h = sk,n(f, 90, ... , 9п)- Оператор (регулярнойсуперпозиции) sk,n является всюду определенным отображением изhследующим образом:если хотя бы одна из частичных функцийФп+I х Ф;+ 1 в Фk и сохраняет вычислимость, т. е. если частичныефункции f Е Фп+l; 90, ...
, 9п Е Фk вычислимы, то и частичная функцияSk,n(J, 90, ... , Оп) вычислима. Верхние индексы у оператора S будутопускаться и вместо S(f, 9о, ... , 9п) будет, как правило, использоватьсяболее привычное, но менее точное обозначение f (90, ... , 9п)Пусть п Е u.1, / Е Фп, 9 Е Фп+2· Определим по f и 9 п + 1-местнуючастичную функцию h так, что для любых m 1 , ... , тп Е u.1h(m1, ... , тп, О)= f(m1, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
