Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 108
Текст из файла (страница 108)
Если мы перейдем от формализма (с') к формализму (7), добавнв сначала о-символы, то можно будет воспользоваться ранее 5 пэиложение а также я установленной нами представимостью рекурсивн ф й'), ых функци ст явной определимостью р-символа через о-сим ') у ранимостью о-символов. Таким образом, в итоге получается, что все квазирекурсивиые функции одного аргумента предста- вимы в (2). Здесь, как и в наших предыдущих результатах, отно- сящихся к квазирекурсивным функциям, как мы отмечали уже в самом началез), можно было бы не ограничиваться рассмотре- нием функций одного аргумента. Действительно, в определении квазирекурсивной функции одного аргумента ее аргумент играет роль параметра; поэтому переход к большему числу параметров является непринципиальным обобщением, так как с помощью рекурсивного перечисления пар чисел, троек чи сколько па раметров всегда могут быть сведены к одному').
Кроме того, следует заметить, что представимость квазире- курсивных функций в формализмах (Е') и (Х) равно как ставнмость рекурсивных функций в (г.), имеет место в более сильном смысле'). Это ). Это следует из представимости квазирекурсив- ных функций в виде уо(р„()(1, и, х)) и из того факта, что , что с по- м лы, щ ф р ул для р-символа могут быть выведены любы фо- улы, получающиеся путем применения схемы (р) о), если в ней р„(1(х) = 0). р„(1(х), а) заменить на р (1(х) 0 й а=к:.х) а р 1( )— У мализмах Х' и Л и становление представимости квазирекурсивных ф функций в фор( ) и ( ) позволяет, в частности, получйтьдоказатель- ство с более об ей щ й точки зрения для ранее установленного ') другим способом утверждения, что функции, введенные посред- ством перекрестных (многократных) рекурсий при добавлении стеме (Х).
характеристик (о-символов) могут быть явно о явно определены в сиСледствием полученного нами нормального представления для регулярно вычислимых функций является тот фак, акт, что каждая и функций вычислима не только в формализме (Ло), но и самом деле, для того в некотором более узком формализме. В самом чтобы иметь возможность для каждой заданной циф ы 1, являю- щейся номером какого-либо нормированного квазирекурсивного определения, вычислять функцию уо(р„()(1, л, х), нам не нужен весь формализм ( ').
Вместо общей схемы примитивной рекурсии ') См. т. 1„с. 533 ) 533 и определенно представимости функпий т ') См. т. 1, с. 48!. о) См. с. 478, сноску 1. о) См. асс пнях, т. 1, с. 396. ) . ра суждение птносйтслыю параметров в рокурсивнм х ппрвдсло. о) См. т, 1, с. 534. ') См. с. 480 и 484 — 485. Х) В связи с этим см. т. 1, с. 509 †!О. ОБШЕРЕКУРСИВНЫЕ ФУНКЦИИ 4 2! нам было бы достаточно взять конечное число рекурсивных равенств, встречающихся в рекурсивных определениях, входящих в !)(1, и, г) функциональных знаков; вместо схемы (!1) и явного определения символа р,г(х) было бы достаточно взять формулы (0) 0(1, и, а) =зйп(()(1, н, а)) 0(1, н, а')+зйп (!>(1, и, а)).а, 0*(1, н) =уо(0(1, и, 0)), которыми вводятся функциональные знаки 0(1, и, а) и 8*(1, н), вместе с рекурсивными определениями встречающихся в этих Равенствах фУнкциональных знаков здп, зйп, +, ° и Уо; а схемУ явного определения можно было бы опустить.
Так мы приходим к некоторому формализму (Еоо), обладающему следующими свойствами: 1. Он получается в результате некоторого ограничения формализма (Хо). (Добавленные исходные равенства (9) выводятся в (2') при помощи явных определений для символов 9 (1, и, а) и 9* (1, п).1 Поэтому из нумернческой непротиворечивости (Ло) следует нумерическая непротиворечивость (Еоо). 2. По своему характеру он является одним из рассматривавшихся до сих пор формализмов, в которых вычисление квазирекурсивных функций осуществляется на основе определяющих эти функции систем равенств. Действительно, каждая формула является равенством между термами; термы строятся из символа О, штрих- символа, индивидных переменных и функциональных знаков; задается конечное число исходных равенств и выводы производятся при помощи правила подстановки и схемы замены').
ПоэтомУ длЯ фоРмализма (Хоо) мы можем использовать постРоеннУю при рассмотрении квазирекурсивных определений нумерацию и определенные со ссылкой на эту нумерацию рекурсивные изображения различных понятий. 3. Каждая регулярно вычислимая функция одного аргумента вычислима в (Хоо). Действительно, каждая такая функция является, как мы знаем, квазирекурсивной, и если 1 является номером ее нормированного квазирекурсивного определения, то она представляется в (2оо) термом 0*(1, н) в том смысле, что для каждой цифры и может быть указана такая цифра г (и притом, вследствие нумерической непротиворечивости (Хоо), только одна такая цифра), что равенство 8*(1, и) =с будет выводимо в (Хоо) Из свойства 2 формализма (2оо) можно, кроме того, извлечь некоторое обращение утверждения 3, состоящее в том, что всякая вычислимаЯ в (2оо) фУнкЦиЯ одного аРгУмента РегУлЯрно вычислима.
х) Схема пеРестановки в (Хоо), квк н в (Зо), ЯвлЯетсЯ пРоизводной схемой 502 ОБЩЕРЕКУРСИННЫЕ фУНКНИИ ПРИЛОЖЕНИЕ 1 г! и1 этого мы покажем, что при вычислении любой Для доказательства функции в (Хгм) для упомянутой в свойстве 2 нумерации выполняются все три условия рекурсивности. Выполнение первого условия устанавливается следую б ы составим какой-либо конечный список исходных равенств формализма (Хее) и возьмем номер 1 этого списка, то необходимое и достаточное условие того, что список формул с номером щ будет представлять собой вывод в (Хье) равейства ной фо м лой 6 , т с номером и, изобразится в его зависимости т р улой ь(1, т, л), которая получится из формулы, ранее обозначенной нами через Е(1, т л), в ре б езультате от расывания относящегося к схеме перестановки члена к)1(у(т, у), у и, х и замены переменной 1 цифрой !.
Как мы знаем аем, отсюда вытекает, что номера выводимых в (2«е) формул образуют область значений некоторой рекурсивной ф ',( ). Эту функцию 1,(л) мы можем определить, например, следующим образом: формула Зе(г„т, л) имеет вид некоторого ),(л) =зйп(йе(У(л, О), У(л, 1))) У(1, О)+ зйп(йе(У(л, О), У(л, 1))) У(л, 1), ние у(п О) то для любой цифры и будем иметь ! (п)=ч( 1), = Р и, ), если значе- (, О) является номером некоторого списка формул в (2«е), являющегося выводом формулы с номером у(п, !), и будем иметь 1„(п) =ч(1, О) в противном случае. В обоих случаях значение !е(п) у й 0 авно но является номером некоторой выводимой в (2 ) фо (, ) равно номеру первой формулы в нашем списке исходных формул формализма (7ее).
Если же г является номером ( ае) формулы и если нг является номером списка формул, представляющего собой вывод этой фо ой формулы «е(щ, г)=0, з|п(йе(нг, г))=0, зап((г (гп г)) У (2'в 3', О) = нг, У (2м 3г, 1) = г, а потому 1«(2~ 3')=г. Таким образом, среди значений функции )а(л) встречается номе любой выводимой в (Еее) формулы и не встречается никаких других чисел. нимости можн Что касается второго условия рекурсивности т ти, то в его выположно убедиться следующим образом: пусть какая-либо вычислимая в (Егм) функция представляется в этом формализме термом !(л); пусть 6 — номер этого терма, а р — номер переменной л; тогда с помощью рекурсивной функции з((т, й, 1), которую мы в свое время определили в связи с построением формулы Е(1, т, л), предикат «число т является номером некоторого равенства !(й)е г с данной цифрой й и некоторой цифрой га может быть переведен в следующий рекурсивный предикат, зависящий от т и й: «существует число х(т, для которого т=10.7м(а Р '").11 а"», Наконец, выполнение третьего условия можно усмотреть непосредственно, точно так же, как это делалось при рассмотрении квазирекурсивных определений.
Тем самым наше утверждение, что каждая вычислимая в(2«е) функция одного аргумента регулярно вычислима, установлено, и поэтому на основании утверждения 3 получается, что совокупность функций одного аргумента, вычислимых в (7«е), совпадает с совокупностью регулярно вычислимых функций одного аргумента, которая в свою очередь, как мы знаем, совпадает с совокупностью квазирекурсивных функций одного аргумента. Замечание. Для формализма (2«) тоже можно показать, что каждая вычислимая в нем функция одного аргумента регулярно вычислима.
Однако доказательство этого факта является более трудным, чем в случае формализма (Хее). Ряд следствий из полученных нами результатов можно извлечь на основе канторовской диагональной процедуры. Применение этой процедуры здесь в известной мере подсказывается тем обстоятельством, что в представлении квазирекурсивных функций одного аргумента термом в' (1, л) участвует — говоря на языке теории множеств — взаимно однозначное соответствие между совокупностью этих функций и некоторым подмножеством натурального ряда. В частности, на этом пути получается следующая доказанная Клини ') Т е о р е м а.
Ое существует такой регулярно вычислимой функции, которая могла бы служить содержательным истолкованием терма )г„()) (л, л, к) =О) формализма (Ег); более того, ло всякой регулярно вычислимой функции одного аргумента 1 (л) можно указать такую цифру 1, что в формализме (21) будет выводима формула с цифрой и, являющейся значением ! (1). ') В уже цитированной работе «бепега! гесцгыуе !ццс!!рпа о! Па!нга! пнщЬег«М теорема ХИ.
504 ПРИЛОЖЕНИЕ г! ! Действительно, всякая регулярно вычислимая функция р у ',(и), как мы знаем, вычислима в (Х!М), а потому то же я одного самое веРно и в отношении фУнкции оа(1(п))+ !. Следовательно, зта функция квазирекурсивна, и для нее можно указать норми- рованное квазирекурсивное определение. Пусть 1 — номер этого определения. Тогда функция оа(1(п))+1 представляется в (Х ) те мом 0*(1, р (, п) и потому если, в частности, и является значе- ОО нием ((1), то в («оа) выводимо равенство 5» (1, 1) = Уа (и) + 1, а также равенство Ра(8(1, 1, 0)) =та(п)+1. Аналогично, в формализме (Еа) выводимо равенство а(й,Ь(1, 1, х))=Та(п)+1, а в (Е!) — равенство о»о»,(1)(1, 1, х) =0) Р Ра(п)+!. Но из этого равенства с помощью выводимой в арифметике, а значит, и в (Х!), формулы рекурсивной оа (а) Ра (Ь) + 1 -~ а ~ Ь получается, что формула п„(1)(1, 1, х)=0)ФП выводима в формализме (Х!).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
