Функция Сколема

Функция Сколема — это математическая функция, используемая в теории рекурсии и теории вычислимости для построения нерекурсивных, но рекурсивно перечислимых множеств. Введена норвежским математиком Туральфом Сколемом в 1944 году в контексте изучения разрешимости арифметических теорий. Функция Сколема является примером функции, которая не является рекурсивной (вычислимой), но её график является рекурсивно перечислимым множеством. Она играет ключевую роль в доказательстве неразрешимости арифметики Пеано и в построении контрпримеров к различным гипотезам в теории рекурсии.

Определение

Функция Сколема, обозначаемая обычно как \( S(n) \), определяется следующим образом. Пусть \( \varphi_0, \varphi_1, \varphi_2, \dots \) — стандартная нумерация всех частично рекурсивных функций одной переменной (например, через машины Тьюринга или системы Поста). Тогда \( S(n) \) — это наименьшее натуральное число \( m \) такое, что \( \varphi_n(m) \) не определено (то есть машина Тьюринга с номером \( n \) не останавливается на входе \( m \)). Если такого \( m \) не существует (то есть \( \varphi_n \) всюду определена), то \( S(n) \) полагается равным 0.

Формально: \[ S(n) = \begin{cases} \mu m \, [ \varphi_n(m) \uparrow ], & \text{если такое } m \text{ существует}, \\ 0, & \text{в противном случае}, \end{cases} \] где \( \uparrow \) означает, что вычисление не завершается.

Свойства

Нерекурсивность

Функция Сколема не является рекурсивной (вычислимой). Доказательство проводится от противного: если бы \( S \) была рекурсивной, то можно было бы построить разрешающую процедуру для проблемы остановки, что невозможно. Действительно, зная \( S(n) \), можно определить, останавливается ли машина \( \varphi_n \) на всех входах: если \( S(n) = 0 \), то \( \varphi_n \) всюду определена; если \( S(n) > 0 \), то \( \varphi_n \) не определена хотя бы на одном входе. Однако проблема остановки неразрешима, поэтому \( S \) не может быть рекурсивной.

Рекурсивная перечислимость графика

Несмотря на нерекурсивность, график функции Сколема \( \{(n, S(n)) \mid n \in \mathbb{N}\} \) является рекурсивно перечислимым множеством. Это означает, что существует алгоритм, который перечисляет все пары \( (n, S(n)) \), хотя и не может вычислить \( S(n) \) для произвольного \( n \). Доказательство основано на том, что можно параллельно запускать все машины \( \varphi_n \) на всех входах, и когда для данного \( n \) обнаруживается, что \( \varphi_n(m) \) не останавливается для некоторого \( m \), то пара \( (n, m) \) добавляется в перечисление. Однако процесс может занять бесконечное время, и для некоторых \( n \) (с всюду определёнными функциями) перечисление никогда не завершится.

Связь с проблемой остановки

Функция Сколема тесно связана с проблемой остановки. Множество \( \{ n \mid S(n) = 0 \} \) — это множество индексов всюду определённых рекурсивных функций, которое является \( \Pi_2 \)-полным в арифметической иерархии. Сама функция \( S \) является примером функции, вычислимой относительно оракула для проблемы остановки.

История

Термин «функция Сколема» введён в 1944 году Туральфом Сколемом в статье «On the existence of a recursive function that is not recursive» (О существовании рекурсивной функции, которая не является рекурсивной). Сколем использовал эту функцию для демонстрации того, что не всякая рекурсивно перечислимая функция является рекурсивной. Ранее, в 1936 году, Алонзо Чёрч и Алан Тьюринг показали неразрешимость проблемы остановки, но Сколем дал явный пример функции, которая не является рекурсивной, но её график рекурсивно перечислим.

Применение

В теории рекурсии

Функция Сколема используется как контрпример к различным утверждениям в теории рекурсии. Например, она показывает, что не всякая функция с рекурсивно перечислимым графиком является рекурсивной. Это служит основой для изучения степеней неразрешимости и арифметической иерархии.

В теории моделей

В теории моделей функция Сколема применяется для построения нестандартных моделей арифметики. С помощью функции Сколема можно показать, что существует нестандартная модель арифметики Пеано, в которой некоторые рекурсивные функции ведут себя нерекурсивно. Это связано с теоремой Гёделя о неполноте и теоремой Сколема о существовании нестандартных моделей.

В теории вычислимости

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

Критика и ограничения

Функция Сколема, хотя и является важным теоретическим примером, не имеет прямого практического применения. Её определение существенно зависит от нумерации частично рекурсивных функций, что делает её чувствительной к выбору нумерации. Разные нумерации могут давать разные функции, хотя все они обладают одинаковыми свойствами нерекурсивности и рекурсивной перечислимости графика. Кроме того, функция Сколема не является всюду определённой в том смысле, что для некоторых \( n \) (например, для индексов всюду определённых функций) значение \( S(n) \) равно 0, что может быть неинформативным.

Источники

• Skolem, T. (1944). «On the existence of a recursive function that is not recursive». Matematisk Tidsskrift, B, 1–9.
• Роджерс, Х. (1967). Теория рекурсивных функций и эффективная вычислимость. McGraw-Hill.
• Сакс, Г. (1990). Теория рекурсии. Springer-Verlag.
• Эндертон, Г. (1972). Математическое введение в логику. Academic Press.