Теория нумераций
Основные понятия
Пусть , , - семейство всех рекурсивно перечислимых множеств n_ок натуральных чисел; вместо часто употребляется просто .
Пусть - семейство рекурсивно перечислимых подмножеств N. Нумерацию этого семейства назовем вычислимой, если множество рекурсивно перечислимо (т.е. ).
Распространим введенное определение на нумерации семейств .
Нумерация семейства , называется вычислимой, если множество рекурсивно перечислимо ().
Предложение 1:
Нумерация , , вычислима тогда и только тогда, когда нумерация свертки семейства , определенная так , является вычислимой. Нумерация , является вычислимой тогда и только тогда, когда нумерация n_развертки семейства определенная так является вычислимой.
Обозначим через , n, семейство всех n_местных частично рекурсивных функций, через - отображение, сопоставляющее функции ее график.
Пусть - семейство n_местных частично рекурсивных функций. Нумерацию семейства назовем вычислимой, если нумерация семейства графиков функций из , определенная так является вычислимой.
Предложение 2
Нумерация семейства n_местных частично-рекурсивных функций вычислимая тогда и только тогда когда частичная (n+1) - местная функция определенная соотношением является частично-рекурсивной.
Функция , связанная с нумерацией некоторого семейства частично-рекурсивных функций является универсальной функцией для , т.е. для любого функция принадлежит и наоборот, для всякой функции существует такое что .
Всякая универсальная функция F для семейства определяет некоторую нумерацию семейства так: . Эта нумерация вычислима тогда и только тогда, когда F частично рекурсивна.
Семейство называется вычислимым если существует по крайней мере одна вычислимая нумерация семейства .
Пусть - две нумерации одного и того же множества S. Говорят что нумерация сводится к нумерации , если существует такая что . Если сводится к , то символически изображаем это так .
Отношение , определенное на множестве H(S) всех нумераций множества S является транзитивным. Следовательно, отношение на H(S) является предпорядком.
Если и для , то эти нумерации эквивалентны и обозначаются . Класс нумераций эквивалентных нумерации обозначим через []. Множество классов эквивалентных нумераций обозначим через L(S).
На множестве H(S) можно задать операцию прямой суммы нумераций . Пусть нумерации , определим нумерацию следующим образом:
Основное свойство операции следующее:
Предложение 3
Пусть тогда сводится к тогда и только тогда когда сводится к и сводится к .
Обозначим через семейство всех вычислимых нумераций и через семейство классов эквивалентных вычислимых нумераций .