Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 105

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 105)

няю Явные определения из выводов нумерически ются легко. Схема замены в формализме (21) в х равенств устрав нем аксиомы (Ю ), п ), ввиду наличия ы ( 1), правила подстановки и схемы заключения, является производйой схемой. А выводимость схе фо ( может быть установлена в (71) с использовани мы рмул ( (р) ления символа (1 (х) и . ьзованием явного опредем а р,( (х), и). Это делается следующим образом.

начала с помощью равенства (1) р» (А (х), и) = р„(и ( х 81 А (х)) мы вводим символ р„(А(х), и). Опираясь на это а фр (') () ул р,', рз) и (р;) получаем формулы мы с помощью этой схемы получим формулы (4) <1(а)чьО-~р„(1(х), а)=р,(1(х), а'), 1(а) =О-+.р,(1(х), а) = а, из которых, далее, с помощью формул Ь=О- зйп(Ь) с+зйп(Ь) а=а, Ь „-ь 0-ю зйп (Ь) ° с+ зйп (Ь) а = с, Ь = 0 ~/ Ь Ф 0 получится формула (5) р„(1(х), а) = здп (1 (а)) р»(1(х),»а')+зяп(1(а)) а. аз=1811(с) =0 с рекурсивным термом 1(с) в результате ряда подстановок вместо индивидных переменных.

Так как в этих подстановках подставляемые термы определены независимо от выбора переменной с именной формы А (с), то мы можем осуществить этот выбор таким образом, чтобы переменная с в упомянутые термы не входила. Тогда мы добьемся того, чтобы в этих формулах, подставляемых вместо формульной переменной А(с) в формулы (рс), (рс) и (рэ) Таким образом, мы можем каждую из получаемых по схеме (р) формул вывести из формул (р,'), (рз) и (р,'), пользуясь средствами рекурсивной арифметики и добавляя к ним одни лишь явные определения. При этом формулы (р,'), (рс) и (р;) используются допустимым в (21) способом.

В самом деле, при выводе формул (2) вместо именной формы А (с) формульной переменной, фигурирующей в этих формулах, требуется подставлять формулу а=-с81А(с), а после этого при выводе формул (4) в получившиеся формулы вместо формульной переменной А (с) надо будет подставить рекурсивную формулу 1(с)= О. Остальные подстановки в выводе интересующей нас формулы (5) мы должны будем производить только вместо индивидных переменных.

Кроме того, так как эта формула не содержит формульных переменных, то при ее использовании в выводе некоторой нумерической формулы после применения к этому выводу операции возвратного переноса подстановок в исходные формулы все подстановки в формулу (5) будут производиться только вместо индивидных переменных. Таким образом, при возвратном переносе в исходные формулы всех подстановок будут производиться только такие подстановки вместо именной формы А (с) в формулы (р',), (р,) и (р,,'), при которых подставляемая формула будет получаться из некоторой формулы 486 НРилОжение 4 П РеГуляРКО Вычислимые Функции.

ФОРмАлизм са) ]и и получающихся из формул вида а ( с 8] 1 (с) = О в результате подстановок вместо индивидных переменных„переменная с никогда не попадала в область действия никакого р-символа. Таким образом, действительно, по любому выводу нумерического равенства, произведенному средствами формализма (Х'), можно построить вывод этого равенства в формализме (2»), и так как этот последний формализм нумерически непротиворечив, то отсюда получается и нумерическая непротиворечивость формализма (Х'). Теперь мы покажем, .что всякая регулярно вычислимая арифметическая функция одного аргумента вычислила в (Ос). В самом деле, пусть нам дана регулярно вычислимая арифметическая функция одного аргумента.

Для нее может быть указан такой формализм Р, в котором она представлена каким-либо одноместным функциональным знаком ](т) или каким-либо выражением ](т) с единственной аргументной переменной, причем это представление таково, что если и является значением этой функции для аргумента а, то равенство ](а)=п выводимо в Р, в то время как для любой отличной от и цифры1 равенство ] (а) =1 в Р невыводимо.

Кроме того, для этого формализма должна иметься такая нумерация, по отношению к которой будут выполняться три упоминавшихся выше условия рекурсивности. Мы будем считать„что нумерация с этим свойством задана, и по очереди воспользуемся всеми тремя этими условиями. Первое из них гласит, что номера выводимых в Р формул образуют область значении некоторой рекурсивной функции ] (п). Пусть 'а — какая-либо цифра, а п — значение рассматриваемой нами функции для аргумента а.

Тогда вследствие выводимости равенства ](а)=п номер этого равенства является некоторым значением функции ](и), т. е. можно указать такую цифру й что значение ](]) будет номером этого равенства. Пусть с — наименьшая из тех цифр 1, для которых значение ](1) представляет собой номер некоторого равенства ((а) = с. Тогда ] (с) является номером некоторого выводимого в Р равенства 1(а)=с, и так как в Р, кроме равенства ](а) =и, невыводимо никакое другое равенство 1(а)=с с какой-либо цифрой с, то с должно совпадать си, а следовательно, и значение ](е) должно совпадать со значением ](]). Второе условие рекурсивности утверждает, что может быть указана такая рекурсивная фермула $(т, и), что для любых цифр 1 н а отношение ])) ((, а) имеет место тогда и только тогда, когда 1 является номером некоторого равенства ((а) = с, где с-цифоа.

Согласно только что доказанному имеет место соотно- шение 143 О (е), а), в то время как для любой цифры 1, меньшей с, отношение Щ(1), а) места не имеет. При этом формула 14) (т, п), будучи рекурсивной, имеет вид р(т, и) =О, где р (т, и) — некоторый рекурсивный терм. Равным образом и выражение р (] (1), а) тоже является рекурсивным термам, а цифра е — наименьшей среди тех цифр й для которых равенство ] (] (]), а) =О имеет место. В соответствии со сказанным в фор- мализме (У') выводимо равенство ]»„р(](х), а)=е, а потому и равенство е=р,р(](х), а). Согласно третьему условию рекурсивности может быть указан такой рекурсивный терм с(п), что для любой цифры 1, являющейся номером некоторого равенства ]=с, значение постоянного терма с(1) равно с, и тем самым в формализме (Х') выводимо равенство с (1) = с.

Так как значение ] (е) представляет собой номер равенства 1 (а) = и, то в (2') выводимо, в частности, равенство с Ц (е)) = и. Но это равенство, взятое вместе с формулой е = ]с р (] (х), е]), с применением схемы замены дает равенство с (] (]» р (] (х), а))) = и. В общем„как следствие выполнения условий рекурсивности получается, что для всякой цифры а в формализме (Е") выводимо равенство с(](р„р(](х), а)))=п, где и — значение рассматриваемой (представленной в Р символом илн выражением ((т)) функции для аргумента а. Таким обра- зом, если с помощью равенства с](п)=с(((р„р(](х), и))) ввести одноместный функциональный знак ]](и) (как мы знаем, в формализме (Е') это допустимо), то для любой цифры а, если п ОГЩЕРЕКУРСИВИЫЕ ФУИКЦИИ 489 ПРИЛОЖЕИИЕ П1 является значением рассматриваемой функции для аргумента а, мы получим в (Е') в качестве выводимой формулы равенство ч(а)=и.

С другой стороны, ни для какой другой, отличной равенство ично от и цифры е 4(а)=е не будет выводимо, потому что в противном случае в (Е') было бы выводимо ложное равенство и=«, в то время как формализм (Е'), как мы это установили н ме и- чески непротиворечив. и, нумериТаким об азом, р, действительно, рассматриваемая нами ь нк- ция, вычислимая в г", вычислима такж (2'), е и в ( ), причем в [Е'1 функ- она изображается некоторым термом а (р,Ь(п, х)), где «(п) и Ь(п, т) — рекурсивные термы с([(п)) н р( (и) п) П „ этом терм Ь (п, и[) обладает тем свойством, что для каждой иь можно указать так ю циф у фру [, ч о мест место отношение а, = . самом деле, для каждой цифры а в г", как мы знаем, выводима формула [(а)=е с некото ой ф этой фо м ле является номе ом этой м лы; фор у можно указать такую цифру [ что зна '([) з ачение [( р ой формулы; а тогда имеет место отношенйе В результате мы получаем, что любая регулярно вычислимая арифметическая функция одного аргумента вычислима также и в (Л') и может быть представлена в виде «( Ь(п, )), переменные, п вчем те м (, ) — рекурсивные термы, содержащие только ко указанные р ерм Ь(пе, п) обладает тем свойством, что для всякой цифры а может быть указана циф а [ такая имеет место равенство Ь(а, 1) = О.

Верно и обратное: если Ь([п, и) — рекурсивный терм, обладающий указанным свойством и зависящий только т ип то тем лько от переменных т рм «(р„Ь(п, х)) изображает вычислимую в (Х') функцию. Действительно, для всякой цифры а ры а после нахождения фр, для которой выполняется равенство Ь(а, [) =О, при помощи перебора цифр от 0 до [ мы найдем наименьшую из таких обознач цифр е, для которых выполняется равенство Ь(и[ )=О. В начить эту наименьшую цифру через е, то в (Р) б димо равенство , то в ( ) удет выво- р,«Ь ([и, х) = е, и если и представляет собой значение рекурсивного терма «(е) без переменных, то равенство «(р„Ь(а, х)) =и также будет выводимо в (Е«), в то время как ни для какой отличной от и цифры е равенство «(р„Ь(и[, х)) =е не будет выводимо в (Р).

Значит, функция а(р Ь(п, х)) действительно вычислима в (У,'). В связи с этим мы рассуждаем еще следующим образом: если какой-либо рекурсивный терм Ь(т, и) удовлетворяет тому условию, что по каждой цифре а можно указать некоторую цифру и такую, что выполняется равенство Ь(а, и) =О, то отношение р Ь(п, х)=[, как это следует из только что проведенного рассуждения, равносильно рекурсивному предикату «имеет место равенство Ь(п, [) = = О и ни для какого г, меньшего [, равенство Ь(п, г) = О места не имеетю Значит, если теперь обозначить этот предикат через 6 (п, [), то число ! будет представлять собой значение изображенной термом р„Ь(п, х) функции в том и только том случае, если можно будет указать такое число и, что имеет место отношение 5(и, [). Но отсюда по одному ранее уже использованному нами замечанию Клини ') получается, что область значений функции, изображенной термом р„Ь(п, х), совпадает с областью значений некоторой рекурсивной функции.

Поэтому то же самое верно и в отношении любой функции, представимой в виде «(р„Ь(п, х)), где «(п) — какая-либо рекурсивная функция. Тем самым из полученного нами результата о представлении в (Р) регулярно вычислимых функций вытекает, что область значений любой регулярно вычислимой функции совпадает с областью значений некоторой рекурсивной функции. Используя квантор существования, мы можем выразить этот факт следующим образом: всякое высказывание вида [х ([ (х) = а), где [ — какая-либо регулярно вычислимая функция, равносильно некоторому высказыванию вида [х(й (х) = а), где й — соответствующая рекурсивная функция. $2. Общерекурсивные и регулярно вычислимые функции. Нормальное представление. Вычисление в формализме (Х««). Применение канторовской диагональной процедуры Полученный нами результат о представимости регулярно вычислимых арифметических функций одного аргумента при помощи термов «([[„Ь(п, х)) формализма (е,«) может вызвать подозрение, что понятие регулярно вычислимой функции было определено нами слишком узко.

') См, с, 348. ПРИЛОЖЕНИЕ и! Чтобы в противовес этом по оз ен у подозрению п дчер ну ь широту нами понятия, мы сравним его с понятия вычислимой ф нкции, п го с другим уточнением обобщен ние понятия ек сивнон имой функции, представляющим собой некото т рое мы удем вдальиейшемназывать обще ек си квазирекурсивной, есл о щерекурсивной или быть указа Я, ой, если для вычисл на система, состоящая из ко числения ее значений может следующего типа: в з конечного числа равенств типа: выражения, стоящие в левой и п а каждого из этих равенств по р ' и правой частях переменных си 0 , построены из сво мвола ,штрих-символа и ф ик и свободных индивидных среди этих функцион фуи циональных знаков; циональных знаков имеется один, 9(п„ ..., п Бс б Ра 3"ачении н °" ° ° .и Ргументов из системы т ыть выведено равенство 9(п„..., и ) где ! представляет собой соответств ю ее э твующее это~у набору р умендля какой отличнои от ! цифры ! 9(л„..., Лг) =! не может быть выведено из Я.

Характеристики

Список файлов книги