Математическая логика и теория алгоритмов

Таким образом, значение il/Cx}") при j=0 определено. Зная значение этой функции при некоторых х и у , молсем определить значение этой функции при х и используя уже схему вычисления значенийф у н к ц и и д л я которой значение приj=0 известно, а при >>>0 можно выразтъ через функцию N, зависящую от аргумен­ та Дх,;'- 1) и т.д. Итак, схему задания примитивно-рекурсивных функций можно рассматривать как процедуру вычисления ее значений. Вычисление ее значений определяется схемой достаточно просто, явно и осущест­ вляется механическим образом. Теорема 6.9. Множество примитивно-рекурсивных функций является счетным множеством, множество общерекурсивных функций |тоже является счетным множеством. Доказательство. Все функции константы ~ примитивно-рекз'р- сивны, следовательно, и общерекурсивны. Тогда их не меньше, чем счетное множество. Доказательство того, что их не более чем счетно, приводится с помощью геделевой нумерации, т.е. удается показать, что каждой общерекурсивной функции молено сопоставить некоторое целое неотрицательное число (геделев номер), причем различным функциям сопоставляются различные числа. Из этой нумерации и следует, что общерекурсивных функций ие более чем счетное множество. Можно доказать следующую теорему, Е Теорема 6.10. Существуют арифметические всюду опреде- знные функции, не являющиеся общерекурсивными функциями, Функция ф от п аргументов называется ч а с т и ч н о - р е к у р с и в н о й , если она может быть получена из исходных функций 1), 2) и 3) с помощью конечного числа подстановок, рекурсий и ц'-оператора, где ц'-оператор определяется так лее, как и ц-оператор, но уже 258