Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Гильберт Д.N. Математическая логика и основания математики
 
djvu / html
 

510 ПОНЯТИЕ «ТОТ, КОТОРЫЙ» И ЕГО УСТРАНИМОСТЬ [ГЛ VIII
(здесь Ъ и п являются выделенными переменными рекурсии, в то время как а выступает только в роли параметра) могут быть разрешены при помощи некоторого терма f (т, п), для которого в (Z) удается вывести равенства
f (Ь, 0) = а + 6,
•f (О, Я') = Р(». l)+e-8gn(6(n)),
f (Ь', п) = f (f (b, п'), п).
Правда, доказательство этого факта нельзя непосредственно извлечь из того метода, с помощью которого мы рассмотрели простейший тип рекурсии, потому что здесь добавляется трудность, заключающаяся в том, что в то время как в случае примитивной рекурсии набор тех значений аргумента а, для которых при рекурсивном вычислении f (и) требуется найти значение f (а), состоит просто из последовательности чисел от 0 до га, в рассматриваемой рекурсии набор пар значений с, d таких, что значение f(c, d) фигурирует в рекурсивном вычислении f (b, п), зависит от пары значений 6, га весьма сложным образом, через посредство некоторого рекурсивного закона.
Поэтому процедура установления разрешимости этих рекурсивных равенств оказывается значительно более запутанной. Однако, как показали фон Нейман и Гёдель, такое доказательство все-таки удается получить 1).
§ 4. Устранимость характеристик (i-символов)
1. Обобщение i-правила; связь с первоначальным i-правилом; термы 1<Ф А(х). Мы рассмотрели вопрос о формализации арифметики в рамках системы (Z) с присоединенной функцией цхА (х) и формулами ((д^), (|д,2), (|д,3) и таким образом ознакомились с возможными способами применения функции ^„А (х), а также получили некоторое представление о формальных возможностях, открывающихся в результате ее введения.
Функция ЦуА (х) в свою очередь определялась нами с помощью i-символа 2), а формулы ((д^), (|д,2), (ц3) мы вывели с помощью i-правила. Тем самым связанные с функцией цхА (х) построения в конце концов сводятся к применениям i-правила.
После этого подробного изложения способов применения i-символа, т. е. формализации понятия «тот, который», мы теперь
J) Изложение этого доказательства по методу фон Неймана было приведено Р. Петер — которая первоначально пришла к этому доказательству другим способом — в ее работе: Peter R. Uber die mehrfache Rekursion.— Math. Ann., 1936, 113, S. 489—527, § 5. (Вместо «перекрестной рекурсии» P. Петер говорит о «многократной рекурсии», и это выражение с тех пор получило права гражданства.)
2) См. с. 481.

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430 440 450 460 470 480 490 500 510 511 512 513 514 515 516 517 518 519 520 530 540 550


Математика