Примитивные рекурсивные функции

Теперь мы определим класс примитивных рекурсивных функций. Это очень интересный класс функций, определенный Геделем для доказательства теоремы неполноты. Нам интересны функции из N^r в N, для r = 0, 1, 2, … Здесь r называется валентность функции, то есть, количество аргументов, которое она принимает. Гедель начал с трех очень простых функций и двух естественных операций над функциями, композиции и примитивной рекурсии, каждая из которых берет очень простые функции и определяет новую. Далее мы приведем определения. Этот раздел технический, и его вполне моно пропустить. Важная идея состоит в том, что примитивные рекурсивные функции составляют очень большой класс вычислимых функций, который может быть построен очень просто.

Мы начнем с трех функций:

• · ж, нулевая функция валентности 0, ж () = 0;
• · з, тождественная функция валентности 1, з (n) = n; and,
• · у, функция валентности 1, у (n) = n +1.

Теперь рассмотрим две операция над функциями:

· Композиция: если f — примитивная рекурсивная функция валентности a, и g₁, …, g_a — примитивные рекурсивные функции валентностей r₁, …, r_a, и k? N, тогда h — примитивная рекурсивная функция валентности k:

h(x₁, …, x_k) = f?(g₁(w₁), …, g_a(w_a)),.

где каждый w_i является списком из r_i аргументов, возможно, с повторами, из x₁, …, x_k; и,.

• · Примитивная рекурсия: если f и g — примитивные рекурсивные функции валентности k и k+2, соответственно, то существует примитивная рекурсивная функция h валентности k+1, удовлетворяющая следующему соотношению:
• o h(0,x₁,…,x_k) = f?(x₁,…,x_k); и,
• o h(n+1,x₁,…,x_k) = g(h(n,x₁,…,x_k), n,x₁,…,x_k).

Композиция является естественным способом подстановки функций, а примитивная рекурсия — ограниченный тип рекурсии, в котором h с первым аргументом n+1 определяется через h с первым аргументом n, а остальные аргументы остаются такими же.

Определим класс примитивных рекурсивных функций как минимальный класс, содержащий начальные функции и замкнутый относительно композиции и примитивной рекурсии.

Примитивные рекурсивные функции очень просто определяются, но очень полезны. Гедель индуктивно доказал, что каждая примитивная рекурсивная функция может быть просто представлена в теории первого порядка. Затем он использовал примитивные рекурсивные функции для того, чтобы закодировать формулы и даже последовательности формул числами.

Чтобы показать, насколько мощно понятие примитивных рекурсивных функций, нужно доказать много лемм. Ниже мы приведем несколько примеров, в частности, докажем, что сложение, умножение и возведение в степень являются примитивными рекурсивными функциями.

Определим сложение P(x,y) следующим образом:

• · P(0,y) = з (y)
• · P(n+1,y) = у (P(n,y))
• ·

Заметим, что это соответствует определению примитивных рекурсивных функций, поскольку функция g(x₁,x₂,x₃) = з (у (x₁)) определяется с помощью начальных функций з и у с помощью композиции.

Далее, определим умножение T(x,y):

• · T(0,y) = ж ()
• · T(n+1,y) = P(T(n,y),y)

Следующей мы определим функцию возведения в степень, E(x,y). (Обычно 0⁰ считается неопределенным, но так как примитивные рекурсивные функции должны быть всюду определены, мы определим E(0,0) равным 1.) Нам нужно два шага, чтобы определить возведение в степень:

• · R(0,y) = у (ж ())
• · R(n+1,y) = T(R(n,y),y)

Наконец, мы можем определить E(x,y) = R(з (y), з (x)) с помощью композиции. (Напомним, что з — тождественная функция, то есть можно просто записать E(x,y) = R(y,x).).

Экспоненциальная функция, E, растет очень быстро, например, E(10,10) равно 10 биллионам, а E(50,50) больше 10⁸⁴ (и это значительно превышает оценку числа атомов во вселенной). Однако, существуют примитивные рекурсивные функции, которые растут гораздо быстрее. Как мы видели, E было определено с помощью медленно растущей функции, у, с помощью трех применений примитивной рекурсии: одна для сложения, вторая — для умножения, третья — для экспоненты. Мы можем продолжать применять примитивную рекурсию для построения очень быстро растущих функций. Давайте сделаем еще один шаг для построения гиперэкспоненциальной функции H(n,m) равной 2 в степени 2 в степени 2 … и так далее, n раз. H примитивная рекурсивная, потому что ее можно определить с помощью E и еще одного применения примитивной рекурсии:

• · H(0,y) = y
• · H(n+1,y) = E(2,H(n,y))

Тем самым, H(2,2) = 2⁴ = 16, H(3,3) = 2²⁵⁶, что больше чем 10⁷⁷ и сравнимо с числом атомов во вселенной. Если это недостаточно большое число для вас, то подумайте о числе H (4,4).