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


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

390 РЕКУРСИВНЫЕ ОПРЕДЕЛЕНИЯ [ГЛ. VII
в том случае, если среди чисел, меньших k, имеются числа со свойством 31 (а), представляет собой наибольшее из таких чисел, а в противном случае он равен числу k. Затем, используя рекурсивно определенную 1) функцию sgn n, мы получим функцию
Min 1 (х) = Min SI (х) . sgn (t (0)),
которая в том случае, когда среди чисел от 0 до А: имеются числа со свойством 21 (а), равна наименьшему из этих чисел, а в противном случае равна О.
3. Делимость; деление с остатком; наименьший отличный от 1 делитель; последовательность простых чисел; разложение числа на простые множители; нумерация конечных последовательностей чисел; нумерация числовых пар; наибольший общий делитель; наименьшее общее кратное. Полученные в результате этого формально-изобразительные и дедуктивные возможности позволяют нам без особого труда перевести в наш формализм многие понятия и доказательства элементарной арифметики. Проиллюстрируем эту мысль на нескольких примерах.
Начнем с понятия делимости. Высказывание «а делится на 6» или «6 делит а» выражает ту мысль, что существует число с, не превосходящее а и такое, что имеет место равенство
а = Ъ -с.
По виду этого высказывания мы без труда можем догадаться, что в нашем формализме оно изобразимо посредством равенства
t = О
такого, что участвующий в нем терм t построен из рекурсивно определенных функций.
Такого рода терм мы будем кратко называть рекурсивным термом, а равенство
t = 0 или же
§ = t,
где § и t — рекурсивные термы, мы будем называть рекурсивной формулой. Подобно этому, всякую функцию, введенную рекурсивно или составленную из такого рода функций, мы также будем называть рекурсивной функцией 2).
*) Повторно эта рекурсия приведена на с. 391.
2) В современной терминологии понятие рекурсивности чаще всего употребляется в смысле общерекурсивноети (в соответствии с определением, приведенным в т. II; см. указание 5 после оглавления т, II), в то время как термы и формулы, рекурсивные в смысле данного нами здесь определения, обычно называются примитивно рекурсивными.

 

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 391 392 393 394 395 396 397 398 399 400 410 420 430 440 450 460 470 480 490 500 510 520 530 540 550


Математика