Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 81
Текст из файла (страница 81)
Определение д(а, Ъ) непосредственно дает нам представимость наибольшего общего делителя а и Ь (при а Ъ Ф 0) в виде Йа — '1 Ь, где Й и с — некоторые числа такие, что Й ( Ь и с ( а. Фигурирующее в этом представлении число Й а удовлетворяет сравнениям Й а=О (шаба) Й.а = Ъ(а, Ь) (шод Ь). В то же самое время мы получаем (а — ' () Ь вЂ” = д(а, Ь) (шоб а), (а — ~).Ь=— О ( д Ь). Отсюда получаем следующие сравнения с переменными г и е: (а — ' () Ь г + /с а е = г.д(а, Ь) (шос( а), (а — ' ().Ь г + Й а г = е д(а, Ь) (шоб Ь).
Это вычисление может быть полностью осуществлено в рамках нашего формализма; действительно, сравнимость чисел вводилась посредством явного определения с помощью функции р (а, Ь). От полученных таким образом сравнений, в левых частях которых, кроме того, терм (а — 'Ь) Ьг+Йае можно заменить термам р ((а — ' 1) Ь г + /с а е), мы придем к выводу формулы, соответствующей высказыванию о том, что при а Ь =ф 0 среди чисел, меньших а Ь, имеется 1 3) некОтОРые ОБОБщения схем РекуРсии и индукции 4я 1гл, чн РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 400 такое число п, для которого имеют место сравнения п = г Ъ(а, Ь) (шой а), и = е Ъ(а, Ь) (шой Ь)> где г и в фигурируют в качестве проиавольных параметров. Если теперь дополнительно наложить условие Ь(а, Ь) = 1, которое выражает в э а и м н у ю простоту чисел а и Ь, т. е. отсутствие у них общих делителей, отличных от 1, то в этом случае мы получим, что среди чисел, меньших а Ь, существует число и, удовлетворяющее сравнениям и = — г (шой а), и=.
( йь) прн проиэвольных г и в. Еще проще, чем приведенные нами теоремы о наибольшем общем делителе получаются теоремы о н а и и е н ь ш е м о б щ е м к р а т н о м. Наименьшее общее кратное чисел а и с Ь может быть рекурсивно определено как «наименьшее иэ тех чисел, не превосходящих а Ь, которые делятся на а и на Ь и отличны от О при а Ь чь Ою Можно привести формальное докаэательство того, что всякое число, делящееся на а и на Ь, делится также и на наименьшее общее кратное чисел а и Ь. Этих примеров достаточно для того, чтобы составить себе представление об этом методе, следуя которому можно осуществить формальное построение арифметики с помощью рекурсий и схемы индукции, но абсолютно бев какого бы то ни было использования свяаанных переменных.
Такой способ наложения арифметики наэывается рекурсивным изложением этой теории, или, для краткости, просто рекурсивной арифметикой, Эта рекурсивная арифметика находится в тесной связи с интуитивной арифметикой, в том виде как мы рассматривали ее в гл. Н, поскольку все ее формулы допускают сбинитное содержатпельное истолкование. Воаможность такого содержательного истолкования вытекает иэ ранее установленной нами верифицируемости всех выводимых формул рекурсивной арифметики.
В самом деле, верифицируемость носит в атом случае характер прямой содержательной интерпретации. Вот почему установление непротиворечивости оказалось здесь таким легким делом. 9 3. Некоторые обобщения схем рекурсии и индукции 1. Рекурсии, допуекаюп4ие сведение к простейшей схеме рекурсии (примитивная рекурсия); рекурсии пробега, одновременные рекурсии. Отличительной чертой рекурсивной арифметики по сравнению с интуитивной теорией являются ограничения, кото- рые накладываются на ее формальный аппарат; она имеет единственный, не считая явных определений, способ образования новых понятий — схему рекурсии; применяемые в ней способы дедукции также подвергнуты сильным ограничениям.
Правда, пе меняя ничего, что было бы характерным для методов рекурсивной арифметики, мы можем произнести определенные обобщения схемы рекурсии, а также схемы индукции. Об этих обобщениях мы н хотели бы немного поговорить. Прежде всего, что касается рекурсий, то мы должны делать различие между такими модификациями схемы рекурсии, которые сводятся к последовательному применению рекурсий ранее рассматривавшегося вида, и такими, допущение которых представляет собой действительное расширение формализма рекурсивной арифметпкп. Рассмотрим сначала несколько таких видов рекурсии, которые хотя и отклоняются от обычной схемы ренурсни ((а,, й, 0) =и(а, ..., Ь), 1(а...., Й, п')=-Ь(а, ...,!с, и, )(а, ..., Й, и)), по все-таки могут быть сведены к рекурсиям, проводимым по этой схеме,— в дальнейшем эти последние мы будем кратно называть прнмитивнылси рекурсиями.
Пример такого рода рекурсии вообще, сводимой к примитивным рекурсиям, представляет собой схема ((В) =-с, 1(п') ==Ь(п, 1(11(и)), ..., с (11(п))), э которой вместо 1 должен быть взят функциональный знак с одним аргументом, а 1,(и), ..., 1,(п) оиозкачают уже введенные термы, для которых выводимы формулы 11 (п) ~4 и, ..., 1, (п) ( и. Сведение этой схемы к примитивным рекурсиям ') производится таким образом, что сначала вместо 1(и) в качестве рекурсивно определяемой функции берется функция (1( )= ИЬ'„""'. в.-н '; Возможность еввдеялл к примитивным рекурсиям длл зтои схемы, в также для рззлссчных других видов рекурсий была показана Рожей Петер (Волниер), См.
доклад; Р е 1 е г В. Ве(сиге(че Рии1сзюиви.— уегЬйи61иияеи йсв ьи(егпй(. Ыв(Ь.-Коиат. Хйг!сЬ, 1932, Ввиб П, 8. 336, з также работу: 1' с 1 е г В. ПЬвг беи ХиваиссивиЬзих бег чвгвсЬ(вйепеи Веэтсде бег гейигв1чеи Росс(с((ол.— Ыв!Ь. Аип,, 1934, 110, 3. 612 — 623. '6 16 Л. Гнзьберт, П. Бернайс 12) некотогык ововщиния схем Рекугсии и индукции «оз [гл, уы РЕНУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 402 Зта функция 1) (и) определяется при помощи следующей примитивяой рекурсии: 1 ) (О) 2« э)п, т)1))а), 1 1а))...,, т))))а), 1 )а))) 1] (и') =- 1) (и) .Ьэ„ Затем 1 (и) получается из 1) (п) с помощью явного определения 1(п) = д) (1)(и), и).
Рассмотренная схема рекурсии представляет собой рекурсию типа «редсурсии пробега», т. е. такой рекурсии, при которой зеачекие 1 (и') аависит ке только от и и 1 (и), по и от всего пробега значений функции 1 до аргумента и. Зту схему, не нарушая ее сводимости к примитивным рекурсиям, мы можем обобщить путем введения параметров, так что получится следунлцая схема: 1(а, ..., 1, 0)=а(а, ...,1), (Я,) 1(а, ..., 1, п')= Ь(а, ..., 1, и, 1(а, ..., 1, 1,(и)), ...,1(а, ...,1, 1,(и))), где снова 1, (и),..., 1 (и) означают термы, для которых выводимы формулы 1, (и) ( п, ..., 12 (п) ~ (и В эту схему (Я,) могут быть, в частности, включены рекурсии следующего вида: 1(а, ..., Х, 0)=с)о(а,, 1), ) (а, ..., 1, 0') =--э,(а,, 1), 1(а, ..., 1, О' )=-э1(а, ..., 1), ((а, ...,1, и~1~ ')=Ь(а, ...,1 и Т(а 1 и) 1(а,, 1, и')...
1(а, ..., 1, и' )), где 1 > 1. Действительно, 1+ 2 равекстэа этой схемы могут быть сведены в следующие два равенства: ((а, ..., 1, 0) = а» (а, ..., 1), 1 (а,..., Х, и') = )) (и', 1) а, (а,..., Х) + ... -)- р (и', 1) а1(а,..., 1) + ваап(1 — 'и).Ь(а, ..., 1, (и — й), 1(а, ..., 1, (и — '1)), 1(а, ..., 1, (и — 1)'), ..., 1(а, ..., 1, (и — 1))1))), а эти равенства уже укладываются в схему (Яд), так как выводимы формулы (и — 1) ( п, (и — '1)' ( п, ..., (п — '$)11)(и. Пример рекурсивных равенств вида (Я,) даст) нам алгоритм Евклида для нахождения наибольшего общего делителя чисел а и Ь. Возникающая в процессе применения этого алгоритма последовательпость равенств а =д, Ь+г„ Ь = а» г, + г„ 1'д = Чэ "2 + "э представляет собой ке что иное, как рекурсивное определеиие некоторой функции р (а, Ь, с), которое производится с помощью функции р(а, Ь) следующими равенствами: р (а, Ь, 0) = а, р (а, Ь, 0') = д, р (а, д, и") = р (р (а, Ь, п), р (а, Ь, п')).
К схеме (Я,) может быть 'сведен другой тип обобщенной рекур- сии — одновременная рекурсия для двух или большего числа функций. Схема одновременной рекурсии в Прос- тейшем случае, когда речь идет о двух одновременно определяе- мых функциях одного аргумента д)) (п) и )1 (п), выглядит следую- щим образом: д)) (0) = ад, )1(0) =аз, «)) (п ) =Ьд (и д()(п) Х(п)) К(п ) =Ьз(п»)) (п) Х(и)). В качестве примера такой одновременной рекурсии мы дадим второе определение для функций о, (и) и о, (и), обращающих фупнцию а (а, Ь), т. е. для тех двух функции, которые в опреде- ленной последовательности сопоставляют числам числовые пары '). Это определение по сравнению с предыдущим будет иметь то преи- мущество, что оно получится непосредственно из процедуры нумерации беэ вспомогательных арифметических рассмотрений; опо выглядит следующим образом: ад (0) = О, а (0) = О, о, (п') = зяп (с)2 (и) — ' од (п)) а (п) + зяп (а, (и) — ' о« (и)) (а.
(п) + 1), о» (и') = эап (о» (и) — ' с)д (и)) -од (п) + здп (од (п) — ' и (и)) ад (и) )д (од (и), ад (и)) (о» (и) + ). ') а . ))5. 26* [гл. чы РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ $ эх некотОРые ОБОБщения схем РекуРсии и индукции 405 Сведение указанной схемы одновременной рекурсии для ф (п) и у (и) к схеме (И,) осуществляется путем написания рекурсивных равенств для функции ~р (и), значения которой определяются равенствами р (2п) = ф (и), ~р (2п+ 1) = у (и). Для етой цели мы используем функцию р (п, 2), которая для четного аргумента принимает значение О, а для нечетного— значение 1, н функцию и (и, 2), которая для четного и удовлетворяет равенству 2 я (и, 2) = и, а для нечетного и — равенству 2 я (и, 2) + 1 = п.
Рекурсивные равенства для ю (п) выглядят следующим образом: <~ (0) = а„ ср (О') = а„ (р (О ) = Ь1 (О, а„а,), ~р (и") = р (и, 2) Ьг (и (и, 2) + 1, ср (и'), ср (и")) + р (п', 2) Ьг (я (и, 2), <р (п), <р (и')). После того как мы т ким образом ввели функцию ~р (п), функции ф (п) и т (и) можно будет получить с помощью явных определений1 ф (п) = ~р (2п), у (и) = ю (2и + 1). Совершенно аналогичным образом к обобщенной схеме рекурсии для одной функции сводится и одновременная рекурсия для нескольких функций; зта рекурсия может также содержать параметры: а,(а, ..., Х, О)=,(а, ...„Х), ЬХ(а, ..., Х, 0)=аХ(а, ..., Х), б, (а, ..., Х, п') = Ь, (а,..., Х, п, а, (а,..., Х, п), ..., ах (а,..., Х, и)), бХ(а, ..., Х, и') =ЬХ(а, ..., Х, и, а, (а,..., Х, п),, 6Х(а, ..., Х, п)).
Для этого сведения устраивается рекурсия для некоторой функции Х (а,..., Х, и), значения которой связаны со аначениями функций б,(а, ..., Х, п), °, аХ(а, ..., Х, п) равенствами Х(а, ..., Х, Х п)=а,(а, ..., Х, п), ((а, ..., Х, Х и+1)Г йг(а, ..., Х, и), ) (а, ..., Х, Х и — , '6(Х)) == ЬХ(а...,, Х, п); при етом нужно воспользоваться функциями р (и, Х) и я (и, Х). Из сводимости одновременной рекурсии к рекурсии вида (1г(г) вытекает также сводимость ее к примитивным рекурсиям. 2. Перекрестные рекурсии; несводимость перекрестных рекурсий определенного типа к примитивным рекурсиям.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
