Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 82
Текст из файла (страница 82)
Кроме рекурсий пробега вида (ЬХ,), схемы (И,) и одновременных рекурсий, имеется много других различных видов рекурсий, допускающих сведение к примитивным рекурсиям. Возникает вопрос, не сводятся лн к примитивным рекурсиям все рекурсии, с помощью которых формализуются те или иные способы последовательного вычисления одной или нескольких функций и которые оказывается возможным изобраанть без введения каких-либо новых типов переменных. На зтот вопрос следует дать отрицательный ответ: могут быть указаны рекурсии, обладающие указанными свойствами и такие, что они не могут быть сведены к примитивным.
В этом можно убедиться двумя различными способами. Один метод — зто канторовская диагональная процедура. Устраивается перечисление всех функций одного аргумента, допускающих определение с помощью примитивной рекурсии. Всякому такому перечислению соответствует некоторая функция двух аргументов у (а, и), обладающая тем свойством, что для каждой цифры Ь функция т (а, Ь) совпадает с той функцией одного аргумента, которая в этом перечислении имеет номер Ь.
Функция т (а, п) не может быть получена с помощью примитивных рекурсий. Действительно, если бы зто было так, то зто же самое было бы справедливо и в отношении функции 2(п,п)+1; но зта функция не может встречаться в рассматриваемом нами перечислении, потому что если бы она имела в нем номер то должно было бы иметь место равенство у,(п, Ь) = т (и, и) + 1, которое при подстановке Ь вместо и привело бы нас к противоречию. Следовательно, если нам теперь удастсн определить зту функцию у (а, и) с помощью какой-либо рекурсии, то тем самым мы получим пример рекурсии, несводимой к примитивным рекурсиям.
РЕКУРСИВНЫЕ ОПРЕДЕЛИ НИ Я з! некОтОРые ОБОБ!цения схем РекУРсии и инДУкци11 407 (гл, чп На этом пути действительно моясно найти рекурсивное опре- деление, обладающее признаками формализованной вычислитель- ной процедуры, с одной стороны, и несводимое к примитивным рекурсиям — с другой. 11равда, построение соответствующего перечисления оказывается весьма трудоемким, но при этом удает- ся воспользоваться тем ранее упоминавшимся фактом, что всякая функция, определимая с помощью произвольных примитивных рекурсий, может быть определена и с помощью таких примитив- ных рекурсий, которые содержат не более одного параметра, и что, следовательно, для перечисления функций одного аргу- мента, определенных с помощью каких-либо примитивных рек сии, достаточно рассматривать рекурсии с не более чем одним параметром.
д» Но в нашем распоряжении имеется и еще один, прямой мета позволяющий устанавливать существование таких рекурсий, кото- рые не сводимы к примитивным. Этот метод, с помощью которого соответствующий пример был впервые построен Аккерманом '), заключается в том, что мы рекурсивно определяем некоторую функцию, относительно которой удается показать, что она растет быстрее, чем любая функция, определимая посредством примитив- ных рекурсий. Функция, для которой Аккерман установил этот факт, полу- чается следующим образом. Строится такая последовательпость функций двух аргументов $ (а, Ь), $, (а, Ь), ..., что ее(а, Ь) =а+Ь, 91 (а, Ь) = а.Ь, $»(а, Ь) =а, а затем (для и ~> 2) ь»1 (а, Ь) определяется с помощью р„(а, Ь) рекурсией йн»1 (а, 0) = а, $н+1 (а, Ь') = $н (а, $н»1 (а, Ь)).
Если рассматривать эту последовательность как функцию трех аргументов 9 (а, Ь, и) = $„ (а, Ь), то для этой функции получаются следующие определяющие равенства: й (а, Ь, О) = а + Ь, $ (а, О, и ) = р (и, 1) + а эяп (6 (и)), $ (а, Ь', и') = $ (а, $ (а, Ь„п'), и). ') А с 1с е г ш а и и йг. Ешп А11ЬеггзсЬеп Ап(Ьзп с(ег гее11еп Еа)в)еп.— Мвсй. Апп., 1928, 99, Лвв 1!2. Эти равенства имеют вид <атерекрестной» рекурсии, т. е. такой рекурсии, которая производится по значениям двух переменных '). Если в этих равенствах вместо и по очереди подставить цифры от О до Ь, то получатся схемы рекурсии обычного типа для функций 9(а,Ь,1), й(а,Ь,2),..., 9(а,Ь,9+1), причем схема для $(а, Ь,1+ 1) содержит введенную предыдущей схемой функцию $ (а, Ь, 1). Таким образом, получается определенная процедура для вычисления значений функции $ (й, Ь, и) для произвольных числовых аначений аргументов, и вычисление значения с, которое $ ( о, Ь, и) принимает для тройки цифр а, Ь и п, с помощью равенств, определяющих функцию 9 (а, Ь, и), может быть переведено в формальный вывод равенства 9 (о, Ь, и) с.
Три указанных определяющих равенства, если в них вместо переменных подставить цифры, а затем повсюду подставить получающиеся в результате процедуры вычисления значения, также перейдут в истинные нумерические равенства. Тем самым перекрестная рекурсия, с помощью которой мы определили $ (а, Ь, п), обладает общими с примитивными рекурсиями свойствами формализованной шагообразной вычислительной процедуры. И тем не менее зта рекурсия не может быть сведена к примитивным з). Действительно, если бы это имело место, то функция 1) Взедепвем соответствующей айннвионалъной переменной можно сле- цующпм образом разложить зту перекрестную рекурскю ка две рекурсии, каждая кз которых прокзводктся по зквчеккям только одной переменной.
Оп»чела рекурсией т (( (х), о, О) = о, т . (( (х), с, и') = 1 (т . (( (х), с, н)) определяется «н-краткзк итерация функции ( (а) с начальным зквчекксвг о», а затем 5 (а, Ь, н) вводится прп помощи рекурсивных рзвепств е (а, Ь, О) = а + Ь, $ (а, Ь, н') = т (Е (а, х, н), () (н, 1) + а вйп (б (и)), Ь Б Однако обе зтк рекурсии уже ке относятся к рассматриваемому кзмк форма- лпзму рекурсивной арифметики.
») В уже упоминавшейся работе (см. сноску ла с. 406) Аккерман уста- кзвлпвает более общий фант — а именно,что для рекурсивного определения фуккцкк $ (а, Ь, и) нельзя обойтись таккмк рекурсиями, которые прок»во- дятся только по значениям какой-либо одной пере»сеялок к ке всполз»уют персмекных более высоких типов. Такие рекурсии — в соответствии с уже упомпкавшпмкся новейшими результвтамк Р. Петер — могут быть сведены к пркмктквкым рекурсиям, к ко»тому установленное Аккерманом свойство упкцкк 5 (а, Ь, и) можно вывести уже кз теоремы о товс, что функция (а, Ь.
и) ле определима прк помощи пркмктпвкых рекурсий. РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ 408 1ГЛ. УП $ (а, а, а) была бы определима при помощи примитивных рекурсии. Однако Аккерман показал, что эта функция растет быстрее, чем любая функция одного аргумента, определимая при помощи примитивных рекурсий. Это принадлежащее Аккерману доказательство существования рекурсивной, но не определимой примитивными рекурсиями функции теперь, с использованием ряда значительных упрощений, произведенных Р. Петер (Полицер), зюжет быть изложено в следующем сокращенном виде. Рассмотрим перекрестную рекурсию г)>(а,О) =2 ° а+1, з(> (О, и') = г(> (1, и), г(> (а', и') =- г)> (г(> (а, и'), п).
Эта рекурсии, как и рассмотренная Аккерманоы рекурсия для функции й (а, Ь, п), тоже обладает свойствами формализованной вычислительной процедуры. Покажем, что определенная с ее помощью функция г(> (а, и) не может быть определена прн помощи примитивных рекурсий. С этой целью мы извлечем из рекурсии для г(> (а, п) ряд полезных для дальней>пего оценок.
Во-первых, для каждой цифры и оказывается выводимым неравенство ') а ( 1)> (а, и). Действительно, неравенство а ( гр (а, 0) может быть получено непосредственно. Если уже выведено неравенство а < г)> (а, п), то из него с помощью подстановок можно будет получить формулы 1 ( ф (1, и), г)> (а, п>) ( г)> (ф (а, и'), и), которые на основании рекурсивных равенств для ф (а, >г) дают неравенства 0 (г(>(0, п'), г)>(а, и') (г(> (а', и'); но из этих неравенств индукцией по а может быть получена формула а<ф(а, н').
') Следует отметать, чта мы здесь пе выводим зту формулу длв переменного и, а лишь содержательна показываем, чта аэа вывадпма лля любой цифры в, Соответствующий вывод для переменного и будет изложен позднее (е. 425) с помощью абабщзппай схемы нэдупцпв. 1,3! НЕКОТОРЫЕ ОПОГЩЕНИЯ СХЕМ РЕКУРСПП Н ННДУКЦНН 48В Пз неравенства а ( гр (а, п) мы получаем а' ( г)> (а, н). Во вторых, для каждан цифры и может быть выведена фор мула а ( Ь -з- г)> (а, и) ( г)> (Ь, ~).
Сначала длн каждой цифры п мы получим г)> (а п) (г)> (а' и) в самом деле, для п --.— 0 это неравенство усматривается непосредственно, а для цифры и, отличной от О, только что укаэанный способ вывода формулы а < г(> (а, п) заодно дает и формулу г(> (а, и) ( г(> (а', п). 'Теперь из формулы г)> (а, п) ( г)> (а', п) мы индукцией по Й выведем формулу г)> (а, п) ( г)г (а + Й', П), а из нее с помощью формулы а(Ьз-Ь = а+(Ь вЂ” 'а')1 искомую формулу а ( Ь ->- г)> (а, н) ( г(> (Ь, и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
