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