Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Из теоремы следует, что примитивно рекурсивные функции образуют достаточно широкий класс всюду определенных функций. Рассмотрим, как можно вычислять значения примитивно рекурсивных функций. Каждая примитивно рекурсивная функция получается из исходных функций 1), 2) и 3) с помощью конечного числа подстановок и рекурсий. Представление функции с помощью подстановки и рекурсии, примененных к исходным функциям, можно рассматривать как набор инструкций для "механического" вычисления значения функций. Следовательно, доказательство примитивно рекурсивности функции является одновременно доказательством существования алгоритма вычисления значений функций. Рассмотрим, например, функцию \i/(x,y) = х«у. Установлено, что у/(х,0) = Z(x)=0; у/(х,у+1) =f( у/(х,у),х), где f(x,y) =х+у. Таким образом, значение у/(х,у) при у=0 определено. Зная значение этой функции при некоторых х и можем определить значение этой функции при х и у+1, используя уже схему вычисления значений функции f(x,y), для которой значение при у=0 известно, а при у>0 можно выразить через функцию N, зависящую от аргумента f(x,y-l) и т.д. Итак, схему задания примитивно рекурсивных функций можно рассматривать как процедуру вычисления ее значений. Вычисление ее значений определяется схемой достаточно просто, явно и осуществляется механическим образом. Теорема 5.9. Множество примитивно рекурсивных функций является счетным множеством, множество общерекурсивных функций тоже является счетным множеством. Доказательство. Все функции константы - примитивно рекурсивны, следовательно, и общерекурсивны. Тогда их не меньше, чем счетное множество. Доказательство того, что их не более чем счетно, приводится с помощью геделевой нумерации, т.е. удается показать, что каждой общерекурсивной функции можно сопоставить некоторое целое неотрицательное число (геделев номер), причем различным функциям сопоставляются различные числа. Из этой нумерации и следует, что общерекурсивных функций не более чем счетное множество. Можно доказать следующую теорему. Теорема 5.10. Существуют арифметические всюду определенные функции, не являющиеся общерекурсивными функциями. Функция (р от п аргументов называется частично рекурсивной, если она может быть получена из исходных функций 1), 2) и 3) с помощью конечного числа подстановок, рекурсий и //' -оператора, где //' - оператор определяется как и /и -оператор, но уже не требуется, чтобы для Vxj, Vx2,..., Vxn существовал;^ 172