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


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

500 ПРИЛОЖЕНИЕ Ш
установленной нами представимостью рекурсивных функций 1), а также явной определимостью |д,-символа через i-символ2) и устранимостью i-символов. Таким образом, в итоге получается, что все квазирекурсивные функции одного аргумента предста-вимы в (Z). Здесь, как и в наших предыдущих результатах, относящихся к квазирекурсивным функциям, как мы отмечали уже в самом начале3), можно было бы не ограничиваться рассмотрением функций одного аргумента. Действительно, в определении квазирекурсивной функции одного аргумента ее аргумент играет роль параметра; поэтому переход к большему числу параметров является непринципиальным обобщением, так как с помощью рекурсивного перечисления пар чисел, троек чисел и т. д. несколько параметров всегда могут быть сведены к одному4).
Кроме того, следует заметить, что представимость квазирекурсивных функций в формализмах (Z1) и (Z), равно как и представимость рекурсивных функций в (Z), имеет место в более сильном смысле6). Это следует из представимости квазирекурсивных функций в виде v0 (fy) (/, п, х)) и из того факта, что с помощью формул для (д,-символа могут быть выведены любые формулы, получающиеся путем применения схемы (|1) в), если в ней \ix(i(x), а) заменить на inx(t(x)==0&a^x), а jX,t(x) — на
Установление представимости квазирекурсивных функций в формализмах (Z1) и (Z) позволяет, в частности, получить доказательство с более общей точки зрения для ранее установленного7) другим способом утверждения, что функции, введенные посредством перекрестных (многократных) рекурсий при добавлении характеристик (i-символов) могут быть явно определены в системе (Z).
Следствием полученного нами нормального представления для регулярно вычислимых функций является тот факт, что каждая из этих функций вычислима не только в формализме (Z°), но и в некотором более узком формализме. В самом деле, для того чтобы иметь возможность для каждой заданной цифры I, являющейся номером какого-либо нормированного квазирекурсивного определения, вычислять функцию v0 (?У) (Г , п, х), нам не нужен весь формализм (Zfi). Вместо общей схемы примитивной рекурсии
!) См. т. I, с. 533 и определение представимости функций, т. I, с. 433 и далее.
2) См. т. I, с. 481.
3) См. с. 478, сноску 1.
*) См. рассуждение относительно параметров в рекурсивных определениях, т. I, с. 396.
б) См. т. I, с. 534.
в) См. с. 480 и 484—485.
?) В связи с этим см. т. I, с. 509—510.

 

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 501 502 503 504 505 506 507 508 509 510 520 530 540 550 560 570 580 590 600 610 620 630 640 650


Математика