1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 51
Текст из файла (страница 51)
, tв исчислении предикатов доказуема секвенцияОчевидно, что из доказуемости секвенции С следует и доказуемостьсеквенции С' = (C)f ( нужно взять доказательство D секвенции СвG и сделать подстановку (D)f, но тогда доказуема секвенция С'== е f--iy С2о (Л(Гj)f,,)). где1t'J= (tj)f ).Рассмотрение случаев, когда последний переход в доказательствеD осуществляется6.5.2. Итак, если вществуют такиеf--поправилуR(Го;наборы... ; Г n)термов1, 2или3 -как впредложениидоказуем пустой список 0, то су-!-kt ; ... ; t ,что доказуемасеквенцияiYI С2о (Л(Гj)~)).
Тогда доказуема секвенция"с~ (М)Из доказуемости такой)> .с~ (ЛГ,))~.секвенции легко выводится,чтодоказуемаи секвенцияоГл.2506.Теория доказательствУкажем теперь, как свести вопрос о доказуемости вформулы Ф исчисленияGGпроизвольнойк вопросу о доказуемости пустого спискав подходящем исчислении резольвент.Если Ф содержит свободные переменныеследствие6.2.3,zo, ... , Zn,то, используялегко проверить,тогда, когда доказуемочто Ф доказуема тогда и толькоуниверсальное замыкание Ф 0 'v'zo ... 'v'znФ фор=мулы Ф.Пусть Ф 0 - замкнутая формула, тогда для нее эффективно находится ей эквивалентная формула Ф 1 , находящаяся в пренекснойнормальной форме. По теореме Эрбрана доказуемость формулы Ф 1(а следовательно, также формул Ф 0 и Ф) равносильна доказуемостиэрбрановой формы Ф}т формулы Ф 1 .
Матрица формулы Ф}т находитсяnв дизъюнктивной нормальной форме, т. е. имеет видГi-V (/\ Гi),гдеi=Oнекоторые списки атомарных формул или их отрицаний. Нотогда Ф}т есть замкнутая :J-формула и, следовательно, ее доказуемостьпо предложению 6.5.3 равносильна выводимости пустого списка 121в исчислении резольвент R(Го; ... ; Г n)Из только что доказанного, теоремы5.4.6и теоремы6.3.5получаем сводимость вопроса о доказуемости произвольной формулы Фвисчислениипредикатовквопросуодоказуемостипустогоспискав подходящем исчислении резольвент.Для машинной реализации поиска доказуемости пустого спискав исчислении резольвент используются различные детерминированные(иногда и недетерминированные) способы последовательного преобразования списков так, чтобы все доказуемые списки были полученыпри таких преобразованиях. Такие способы носят названия стратегийпоиска. Обсуждение каких либо стратегий выходит за рамки нашегоучебника.Для того чтобы хоть немного почувствовать возникающие здесьпроблемы, предлагается доказать следующее утверждение.Предложение6.5.4.Существует алгоритм, который по двумформулам Ф и Ф исчисления резольвент узнает, существуют литакие наборы термовt = t,, ...
, tn,что формулы ( Ф )f и (Ф)f совпадают, и если такие наборы существуют, то находит универсальный такой наборt.Х(ф) t'= (•Т,)Х"' I',"существует такоиствующий списку ичтоt' = (t)f,,.=ио,... , Uk_,t такого, что-t/1 = t 011 , ..• , t 11k, соответпеременных термов из t,Универсальность означает, что для любого наборана б ор термовсвободныхоГлава7вычислим ость§ 7 .1.Понятие алгоритмаВ предыдущих главах мы неоднократно говорили об алгоритме Qt,действующем на некотором множестве объектов Х, понимая под этимточное предписание, определяющее по любому объекту а Е Х некоторую вполне определенную последовательность простейших действий,осуществляя которые,мы либо никогда не закончимэтот процесс(вычисления), либо этот процесс заканчивается и мы получаем объектQt(a),называемый значением Qt на а, либо процесс обрывается безполучения значения.
Если процесс, определяемый алгоритмом21поэлементу а, не заканчивается или обрывается без получения значения,то говорят, что Qt не применим к а. Примерами алгоритмов могутслужить правила сложения, умножения и деления, действующие намножестве пар натуральных чисел. Заметим, что алгоритм деления неприменим к паре натуральных чисел (п,наm.m),если п не делится нацелоДругим примером является описанный в§ 4.3алгоритм нахождения по формуле исчисления предикатов эквивалентной ей формулы,находящейся в пренексной нормальной форме. Количество простейшихдействий,необходимыхдляполучениязначенияалгоритма,можетбыть весьма большим. Однако мы отвлекаемся (абстрагируемся) наданном уровне изучения от реальных возможностей осуществления алгоритмов и будем исходить из предположения, что при осуществлениипроцессавычисления,определенногоалгоритмом,мыимеемнеограниченный запас времени и материалов. Такое предположение носитназвание принципа потенциальной осуществимости.Как правило, интуитивного понимания бывает достаточно для установления того, является ли данное предписание алгоритмом илинет.Однако без точного определения алгоритма невозможно обойтись, еслипытаться доказывать, что для решения определенного класса задач несуществует единой эффективной процедуры (алгоритма).
Но возможноли найти такое математическое определение понятия алгоритма, чтобыи охватить все разнообразие уже существующих алгоритмов и эффективных процедур, накопленных математической и вычислительной252Гл.7.Вычислимостьпрактикой, и быть уверенным, что любой предложенный в будущеминтуитивноприемлемый алгоритмподпадает под это определение?Поставленный столь широко вопрос вряд ли имеет положительноерешение.
Однако реальное развитие математики привело к удовлетворительному решению (точнее было бы сказать снятию) этой проблемы. А именно, было предложено несколько формализаций понятияалгоритма, различающихся возможными областями действия, наборомдопустимых простейших действий и возможностями составления предписаний (программ) для вычисления. Изучение этих формализацийпоказало, что они обладают свойствамизамкнутости относительновсевозможных комбинаций (суперпозиции, итерации и т.
п.), большими возможностями воспроизводить с достаточной степени похожести(адекватности) все известные алгоритмические процедуры и приемы.Наиболее существенным для оправдания определений оказалось совпадение классов вычислимых функций для всех этих понятий. Поэтому по крайней мере понятие (алгоритмически) вычислимой функции(снатуральными аргументами и значениями) оказалось инвариантноопределенным и для теоретических целей этого вполне достаточно.Существование ряда различных определени~ (уточнений) понятия алгоритмимеетисвоипреимущества,таккакдлярешенияразличныхзадач бывает удобно использовать различные, наиболее подходящиедля этого случая, определения. Аналогию этому явлению можно найтив программировании-существующее многообразие языков программирования во многом объясняется разнообразием задач, стоящих передвычислителями и программистами.В этойглаве будут даны определения для трех различных, ноэквивалентных подходов к понятию алгоритмической вычислимости.За основу первого подхода, отступая от традиций, берется понятиеЕ-определимости.
Традиционные уточнения понятия вычислимостимашины Тьюринга и рекурсивные функции--будут приведены в конценастоящей главы.§ 7.2.:Е-предикаты и :Е-функции на!1Пусть П ::::с; (w, О, s, +, ·, ~) - алгебраическая система сигнатурыu0 = (О, s 1 , +2 , -2 , ~ 2 ), основным множеством которой является множество натуральных чисел (конечных ординалов), символы О,+,·,~ имеют обычный смысл, а функция s 11 : w--, w такая, что s 11 (n)п1 для= +всех п Еw.Изучение Е-функций удобно проводить в более широкомклассе частичных Е-функций.Напомним, что под частичной функцией мы понимаем здесь всякоеотображениеf:Х --, w, где Х ~ wk для некоторого k Е w. Число§ 7.2.k"Е-предикаты и "Е-функции на253S1в этом случае называется местностью частичной функцииобозначается черезбудем называтьделенной при Хf нигде= wv(f).f:Еслиv(f).Х -+ w -fичастичная функция, то=не определенной при Х0 и всюду опре1) Всюду определенную частичную функциюв дальнейшем будем называть просто функцией.
Частичную функциюместностиkбудем называть k-местной частичной функцией. Мы= О.допускаем случай, когда kбудет состоять из одной парыТогда О-местная функция(0, п)f:w 0 -+ wдля некоторого п Е w и часто будетотождествляться с числом п. Всюду в дальнейшем буквыm, k, п, iиj,возможно с индексами, будут обозначать натуральные числа.Пусть f: Х -+ w - k-местная частичная функция. Если (m1, ...... ,mk) Е Х, то f(m1, ...
,mk) - это значение функции f на наборе(m1, ... ,mk). Если (m1, ... ,mk) i Х, то будем говорить, что !(т1, .. .. . . , mk) не определено или что f не определена на наборе (т1, .. .... ,mk).Ясно, что для задания частичной k-местной функции f достаточнодля любого набора (m1, ... ,mk) сказать, определено лип= f(m1, .... . .
, mk)- Если f и g - частичные функции, то будем писатькогда обе части равенства определены и равны, либо обе части равенства не определены.Пусть k>Ои Х ~ wk.Определение. (Частичная) k-местная функцияся(частичной)g:Х -+ w называетЕ-функцией, если ее графикГ 9 :с=; { (mo, ... , mk-1,mk) 1 mo, ... , mk-1ЕX,g(mo, ... , mk-1) = mk}есть Е-предикат на П.Множество Х-область определения функции g -будем обозначать через д 9 .Укажем простейшие факты о (частичных) Е-функциях.(1)Следующие функции0: w-+ w и I'f:: wn-+ w,где п> О, k < п,являются Е-функциями:0(i)=0, iEw,I'f:(ia, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
