1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 59
Текст из файла (страница 59)
, тп);298Гл.7.Вычислимостьh(m1, ... , тп, k + 1) не определено, если h(m1, ... , тп, k) не опредеh(m1, ... ,mп,k+ 1) = g(m1, .. ,,mп,k,h(m1, ... ,mп,k)), еслиh(mi, ... , тп, k) определено. Очевидно, что h однозначно определеналено иfпои g и вычислима, если вычислимыfи g.
Указанное определениеh по f и g задает оператор Rn+I: Фп х Фп+2 ---. Фп+l, который назовемоператором примитивной рекурсии. Про функцию h = Rп+ 1 (J,g)будем говорить, что она получена примитивной рекурсией из функцийf и g. Верхний индекс у оператора Rn+I будем опускать.Пусть п Е 1.v, f Е Фп+I · Определим по f такую п-местную частичную функцию g, что для любых k, m1, ...
, тп Е w, g(m1, ... , тп) = kтогда и только тогда, когда f(m1, ... , тп, О) = О и k = О или k > Ои f(m1, .. ,,mп,O), ... ,f(m1, ... ,mп,k- l) определены и не равны нулю, а J(m1, ... , тп, k) = О. Ясно, что такая функция g существуети однозначно определена по f; кроме того, если f вычислимаяфункция, то из определениязадан оператор мпg=-g видно, как вычислять g. Таким образом,оператор минимизациимп(!), то будем говорить, чтоg-из Фп+l в Фп; еслиполучена минимизацией изБазисными функциями называются функции о,где оние О,п-s, 1:;:. (1~mf.~ п),одноместная функция, которая на любом п принимает значеs -одноместная функция, принимающая на числе п значение+ 1, а 1:;:. -n-местная функция, принимающая на наборе(k1, ...
, kп)значение kт. Очевидно, что базисные функции вычислимы.Определение. Частичная функцияfназывается частично рекурсивной, если существует такая конечная последовательность частичных функцийgo, ... , gk,чтоgk=fи каждаяgi, i~k,либо базисная, либо получается из некоторых предыдущих регулярной суперпозицией, примитивной рекурсией или минимизацией. Эта последовательностьдляf.go, ... , gkназывается определяющей последовательностьюВсюду определенная частично рекурсивная функция называетсярекурсивной.Можно доказать, что для любой рекурсивной функции существуетопределяющая последовательность,состоящая толькоизвсюдуопределенных функций.Из данного определения и приведенных выше замечаний о сохранении вычислимости операторамиS, R, Млегко следует, что всякаячастично рекурсивная функция является вычислимой.Обратное утверждение носит название тезиса Чёрча: Любая вычислимая частичная функция частично рекурсивна.Исторически именно это утверждение было первым точным математическим определением понятия алгоритмически вычислимой функции.Изно,пунктов(1), (2), (9), (10),установленныхчто любая частично рекурси1:наяв§ 7.2, очевидфункция являетсячастичной§ 7.
7.Рекурсивные функции299Е-функцией. Справедливо также обратное утверждение, доказательство которого мы опустим из-за его громоздкости: любая частичнаяЕ-функция является частично рекурсивной.Тем самым, имеет место следующая теорема.Теорема7. 7 .1.Класс частично рекурсивных функций совпадаетс классом частичных Е-функций.Таким образом, тезис Тьюринга эквивалентен тезису Чёрча.Глава8РАЗРЕШИМЫЕ И НЕРАЗРЕШИМЫЕ ТЕОРИИТеорема7.5.1)онеразрешимостиэлементарнойарифметики(теоремаположила конец попыткам построить универсальный алгоритмрешения всех математических задач. Однако нахождение алгоритмовдля решения различных классов математических задач было и остаетсяодной из важнейших целей математики.
Построенные в математической логике формальные языки значительно расширили возможностинахождения классов задач с разрешающим алгоритмом. В частности,про любую элементарную теорию Т мы можем спросить, разрешима лиона, т. е. существует ли алгоритм, устанавливающий по любому предложению r.p, принадлежит ли r.p данной теории Т. К сожалению, многиеважные для математики теории оказались неразрешимыми. Вбудет продолжен список неразрешимых теорий, начатый в§ 8.6§ 7.5, ибудут приведены плодотворные методы доказательства неразрешимостиэлементарных теорий. Вместе с тем, в§ 8.1-8.5 на нескольких важныхпримерах будут продемонстрированы некоторые методы доказательстваразрешимости элементарных теорий.§ 8.1.Разрешимость теории одноместных предикатовВ этом параграфе мы докажем разрешимость теории класса всехмоделей сигнатуры Е 1=(Ро,Pi, ...
),состоящей из счетного числа одноместных предикатов, и опишем все полные теории этой сигнатуры.Вначале докажем один факт более общего характера, который будетиспользоваться также в других параграфах.Предложение8.1.1.Пусть Го-множество предложений некоторой сигнатуры Е, замкнутое относительно конъюнкции, дизъюнкции и отрицания.
Пусть То-некоторая теория сигнатуры Е идля любой полной теории Т сигнатуры Е, являющейся расширениемтеории То, и любого Ф Е Т выполнено условие (Тоu (Го n Т))!> Ф.Тогда для любого предложения Ф сигнатуры Е существует предложение Ф* Е Го, для которого выполнено То!> (Ф +-+ Ф*)(через(Ф +-+ Ф*) обозначается формула (Ф -+ Ф*) 1\ (Ф* --> Ф)).
При этом§ 8.1.Теории одноместных предикатов301если существует алгоритм перечисления предложений теории То,то существует алгоритм получения предложений Ф* по предложениям Ф.До к аз ат ел ь ст в о. Рассмотрим множество предложенийУ= ГФПокажем, что множествочто множествоZIФZ=Е Го, (ТоТоU {Ф}) 1> Ф}.U У U { Ф} несовместно. Предположим,4.4.4 существует полнаясовместно.
По предложениютеория Т, содержащая множество предложенийусловию мы имеем (ТоU (Гоn Т)) l> Ф.Z.Так как Ф Е Т, то поПо определению отношения 1>и замкнутости множества Го относительно конъюнкции мы получаем(ТоU {Фо})l> Ф для некоторого Фо Е Тn Го.Следовательно, ~Фо Е У.Так как У~ Т, то ~Фо Е Т. Это невозможно в силу непротиворечивости Т и условия Фо Е Т.Таким образом, мы имеем (Торых Ф1,... ,Фпчто для формулы Ф*То l> (Фt-tU {~Ф1, ... , ~Фп}) 1> ~Ф для некотоi Е {1, ...
,п}. Ясно,Е Го с условиями (ТоU{Фi})!>Ф,=(Ф IV ... V Ф п)будет выполняться свойствоФ*).Алгоритм нахождения предложения Ф* состоит в эффективном перечислении всех предложений теории То пока не появится предложениевида (Фt-tФ*), где Ф* Е Го.DРассмотрим сигнатуру Е~ ;=; (Ро, ...
, Рп) ~ I: 1. Для любого кортежас= (со,... , сп)длины п+ 1, состоящего из нулей и единиц, через ре: (х)обозначим формулуPlгде, как обычно, Р 0 (х)ная формула, т>0(х)=/\Р{' (х)/\ ... /\ p~n (х),~Р(х), Р 1 (х)= Р(х).Пусть Ф -произвольО.
Формулуобозначим через 3тх Ф(х), где 31х Ф(х) означает 3х Ф(х).Определение. Будем говорить, что формула Фо является булевойкомбинацией формул из класса Г, если она принадлежит наименьшемуклассу формул, содержащему Г и замкнутому относительно взятияконъюнкций, дизъюнкций и отрицаний.Пусть Го-множество всех предложений, являющихся булевымикомбинациями предложений вида 3mx ре: (х), где m Е w, с Е {О, 1}(п+I).Гл.302ПредложениеХ= Т n Го.8.Разрешимые и неразрешимые теории8.1.2. Пусть Т - полная теория сигнатуры:E!iиТогда для любого предложения Ф Е Т выполнено Х [> Ф.До к аз ат ел ь ст в о. Пусть теория Т1 является замыканием множества Х относительно выводим ости.
Нужно показать, что Ткак Т1<;;;<;;;Т1. ТакТ, то достаточно показать, что теория Т1 полна.Так как Т- полная теория, то для любого Е Е {О, 1}(n+I) и любых21и ~ не более чем счетной мощности множества Р 0 (21)Т-моделейи Р 0 (~) имеют одинаковую мощность. Так как эти множества непересекаются и покрывают носители этих моделей, то любое биективное отображениеf:А-.
В, переводящее для каждого с Е {О, 1}(n+I)множество Р 0 (21) в множество Р 0 (~) будет изоморфизмом системIP 0 (21)1 = kи~- Заметим, что условие(3kxP 0 (x) /\ ~3(k+l)xP 0 (x)), а условиемножеством предложений {3kx Р 0 ( х)121Е w записывается предложениемkIP 0 (21)1?: w - бесконечнымw}. Таким образом, либо всеЕТ1 -модели конечны и изоморфны, либо теория Т1 счетно категорична.По предложениям3.2.
7и5.6.1теория Т1 полна.ОПредложение 8.1.3. Для любого предложения Ф сигнатурысуществует предложениеw Е Го,До к аз ат ель ст в о. Предложение вытекает из предложенийи8.1.2,:E!iкоторое эквивалентно Ф.8.1.1где в качестве То берется множество предложений сигнатуры:E!i, являющихся теоремамиДля предложенияwисчисления ИПr:~.ОЕ Го пусть т(w) обозначает такое наибольшеенатуральное число m, что предложение 3mx Р 0 (х) является подформулой предложенияw.Лемма 8.1.4 Для любой системасуществует система21[m]для любого предложенияw21 сигнатуры :E!i и любого т Е:;,;; т · 2п такая, чтоЕ Го с условием т(w)До к аз ат ель ст в о.
Ясно, что в качествесистему системы21,::;;; m.21[m]можно взять подполученную уменьшением множеств Р 0 (21), длякоторых выполнено IP0 (21)1 > m, до множеств мощностинием множеств Р 0 (21), для которых выполнено IP 0 (21)1::;;;Предложениеwмощностиm сm.сохране·О8.1.5. По любому предложению сигнатуры :Е 1можно эффективно узнать, является ли оно тождественно истинным.До к аз ат ель ст в о. Пусть Ф - предложение сигнатуры :Е 1 .
ТогдаФ является предложением сигнатурыдля некоторого п Е w. Так как:E!i§ 8.2.Алгебраически замкнутые поля303существует эффективная процедура выписывания доказуемых секвенций сигнатуры Е~, то по предложению 8.1.3 мы можем эффективно\f/ Е Го, которое эквивалентно Ф. Пусть m = т(\fl).найти предложениеТак как свойство тождественной истинности сохраняется при переходек эквивалентным формулам, то в силу леммыистинность предложения Ф равносильна егоПроверка этого свойства(предложение8.1.4тождественная(m · 2п )-общезначимости.осуществляется законечное число шагов3.2.8).DИз предыдущего предложения и теоремы о полноте исчисленияИПЕ' вытекаетТеорема 8.1.6. Исчисление предикатов сигнатуры Е 1 разрешимо.Упражнения1.ПустьГ1-булевакомбинацияформул.
Доказать, что если Ф(хо,:3хоФ(хо,... , хп)формул... , хп)изГоиатомарныхЕ Г,, то по формулеможно эффективно построить эквивалентную ейформулу из Г 1 . (Указание. Использовать индукцию по длинеформулы.)2.Используя упражнениезуя предложения8.1.11, доказать предложение 8.1.3, не исполь8.1.2, причем указанное предложение \f/инаходится эффективно.§ 8.2.Элиминация кванторов и разрешимость теорииалгебраически замкнутых полейРассмотрим теорию АЗП сигнатуры и f=(О,-1, +, ·),аксиомамикоторой будут аксиомы теории полей вместе со всеми предложениямивида'v'xo ... 'v'Xn-1:Jy (уп+ Xn-lYn-l + ... + х,у +хо~ О),nЕW \{О}.Модели теории АЗП в алгебре называются алгебраически замкнутыми полями.В данном параграфе будет доказана следующаяТеорема8.2.1.Теория АЗП допускает элиминацию кванторов.До к аз ат ел ь ст в о.Для элиминации кванторов достаточно по-казать, что бескванторной формуле эквивалентна относительно АЗПвсякая формула Ф вида:3хгдеk fI -(6(fi~ J:)термы сигнатуры UJ, бi Е {О,0; ) ,1}.Гл.3048.Разрешимые и неразрешимые теорииПоскольку в теории АЗП имеет место~ О/\~t'~ О= ~ t · t' ~ О,(t~t')= (t -t'~ О), а~t~можно считать, что формула Ф имеет вид3х с~ fi ~ О /\ g ~ О)для некоторых термов/1, ...
, fk, g.Заметим, что любой термсигнатуры а! <<эквивалентен~ некоt(u)торому полиному с целыми коэффициентами, т. е. из теории АЗПвыводится формула~t(u)t' (и)для некоторогоt' (и)ЕZ[u].Такимобразом, для доказательства элиминации кванторов в АЗП можнорассматривать лишь формулы с термами изПустьt(x, у) -ненулевой терм изZ[u].Z[x, у].Тогдаt(x, у)записываетсяв виде+ tn-1(y)xn-l + ... + to(y),tn(y)xnгде tп(У) ЕZ[y] \{О}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
