Примитивные рекурсивные функции
Теперь мы определим класс примитивных рекурсивных функций. Это очень интересный класс функций, определенный Геделем для доказательства теоремы неполноты. Нам интересны функции из Nr в N, для r = 0, 1, 2, … Здесь r называется валентность функции, то есть, количество аргументов, которое она принимает. Гедель начал с трех очень простых функций и двух естественных операций над функциями, композиции и примитивной рекурсии, каждая из которых берет очень простые функции и определяет новую. Далее мы приведем определения. Этот раздел технический, и его вполне моно пропустить. Важная идея состоит в том, что примитивные рекурсивные функции составляют очень большой класс вычислимых функций, который может быть построен очень просто.
Мы начнем с трех функций:
ζ, нулевая функция валентности 0, ζ( ) = 0;
η, тождественная функция валентности 1, η(n) = n; and,
σ, функция валентности 1, σ(n) = n +1.
Теперь рассмотрим две операция над функциями:
Композиция: если f - примитивная рекурсивная функция валентности a, и g1, …, ga - примитивные рекурсивные функции валентностей r1, …, ra, и k∈ N, тогда h – примитивная рекурсивная функция валентности k:
h(x1, …, xk) = f (g1(w1), …, ga(wa)),
где каждый wi является списком из ri аргументов, возможно, с повторами, из x1, …, xk; и,
Примитивная рекурсия: если f и g – примитивные рекурсивные функции валентности k и k+2, соответственно, то существует примитивная рекурсивная функция h валентности k+1, удовлетворяющая следующему соотношению:
h(0,x1,…,xk) = f (x1,…,xk); и,
h(n+1,x1,…,xk) = g(h(n,x1,…,xk), n,x1,…,xk).
Композиция является естественным способом подстановки функций, а примитивная рекурсия – ограниченный тип рекурсии, в котором h с первым аргументом n+1 определяется через h с первым аргументом n, а остальные аргументы остаются такими же.
Определим класс примитивных рекурсивных функций как минимальный класс, содержащий начальные функции и замкнутый относительно композиции и примитивной рекурсии.
Примитивные рекурсивные функции очень просто определяются, но очень полезны. Гедель индуктивно доказал, что каждая примитивная рекурсивная функция может быть просто представлена в теории первого порядка. Затем он использовал примитивные рекурсивные функции для того, чтобы закодировать формулы и даже последовательности формул числами.
Чтобы показать, насколько мощно понятие примитивных рекурсивных функций, нужно доказать много лемм. Ниже мы приведем несколько примеров, в частности, докажем, что сложение, умножение и возведение в степень являются примитивными рекурсивными функциями.
Определим сложение P(x,y) следующим образом:
P(0,y) = η(y)
P(n+1,y) = σ(P(n,y))
Заметим, что это соответствует определению примитивных рекурсивных функций, поскольку функция g(x1,x2,x3) = η(σ(x1)) определяется с помощью начальных функций η и σ с помощью композиции.
Далее, определим умножение T(x,y):
T(0,y) = ζ( )
T(n+1,y) = P(T(n,y),y)
Следующей мы определим функцию возведения в степень, E(x,y). (Обычно 00 считается неопределенным, но так как примитивные рекурсивные функции должны быть всюду определены, мы определим E(0,0) равным 1.) Нам нужно два шага, чтобы определить возведение в степень:
Наконец, мы можем определить E(x,y) = R(η(y),η(x)) с помощью композиции. (Напомним, что η – тождественная функция, то есть можно просто записать E(x,y) = R(y,x).)
Экспоненциальная функция, E, растет очень быстро, например, E(10,10) равно 10 биллионам, а E(50,50) больше 1084 (и это значительно превышает оценку числа атомов во вселенной). Однако, существуют примитивные рекурсивные функции, которые растут гораздо быстрее. Как мы видели, 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) = 24 = 16, H(3,3) = 2256, что больше чем 1077 и сравнимо с числом атомов во вселенной. Если это недостаточно большое число для вас, то подумайте о числе H(4,4).
3.1 Рекурсивные функции
Множество примитивных рекурсивных функций – это огромный класс вычислимых функций. На самом деле, их можно описать как множество функций, вычислимых за то же время, что и некоторая примитивная рекурсивная функция от n, где n - длина входа. Например, так как H(n,n) – примитивная рекурсивная функция, примитивная рекурсивная функция включает все функции из класса TIME[H(n,n)]. (в следующем разделе обсуждаются классы вычислимых функций, в том числе и TIME.) Тем самым, примитивные рекурсивные функции включают все функции, вычислимые в смысле любой более-менее разумной меры, и даже больше этого.
Однако, примитивные рекурсивные функции не включают все функции вычислимые в принципе. Чтобы доказать это, мы снова можем использовать диагонализацию. Мы можем закодировать все определения примитивной рекурсивной функции валентности 1, обозначив их p1, p2, p3, и так далее.
Мы можем построить машину Тьюринга для вычисления диагональной функции D(n) = pn(n) + 1.
Заметим, что D всюду определенная вычислимая функция из N в N, но она не является примитивной рекурсивной функцией. Почему? Предположим, что D – примитивная рекурсивная функция. Тогда D будет равна pd для какого-нибудь d∈ N. Тогда из этого будет следовать, что
pd(d) = pd (d) +1,
противоречие. Тем самым, D не примитивная рекурсивная функция.
Приведенный выше метод работает для любого класса всюду определенных функций. Единственный способ обойти это, если мы хотим получить множество всех функций вычислимых в принципе, а не только на практике, - добавить что-то типа неограниченной операции поиска. Это то, что сделал Гедель для расширения класса примитивных рекурсивных функций до рекурсивных функций.
Определим неограниченный оператор минимизации μ. Пусть f – возможно частично определенная функция валентности k+1. Тогда μ[f] определяется как следующая функция валентности k. На входе x1, …, xk:
For i = 0 to ∞ do {
if f(i,x1,…,xk) = 1, then return i
}
То есть, если f (i,x1,…,xk) = 1, и для всех j < i, f (j,x1,…,xk) определена но не равна 1, то μ [f ](x1, …, xk) = i. Иначе μ[f ](x1, …, xk) не определена.
Гедель определил множество рекурсивных функций как замыкание начальных примитивных рекурсивных функций относительно композиции, примитивной рекурсии и μ. Определяя рекурсивные функции таким образом, мы получаем в точности множество частично определенных функций, вычислимых в  – исчислении, в формальных системах Клине, алгоритмами Маркова, машинами Поста и машинами Тьюринга.
|
