Теория нумераций

реферат

Основные понятия

Пусть , , - семейство всех рекурсивно перечислимых множеств n_ок натуральных чисел; вместо часто употребляется просто .

Пусть - семейство рекурсивно перечислимых подмножеств N. Нумерацию этого семейства назовем вычислимой, если множество рекурсивно перечислимо (т.е. ).

Распространим введенное определение на нумерации семейств .

Нумерация семейства , называется вычислимой, если множество рекурсивно перечислимо ().

Предложение 1:

Нумерация , , вычислима тогда и только тогда, когда нумерация свертки семейства , определенная так , является вычислимой. Нумерация , является вычислимой тогда и только тогда, когда нумерация n_развертки семейства определенная так является вычислимой.

Обозначим через , n, семейство всех n_местных частично рекурсивных функций, через - отображение, сопоставляющее функции ее график.

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

Предложение 2

Нумерация семейства n_местных частично-рекурсивных функций вычислимая тогда и только тогда когда частичная (n+1) - местная функция определенная соотношением является частично-рекурсивной.

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

Всякая универсальная функция F для семейства определяет некоторую нумерацию семейства так: . Эта нумерация вычислима тогда и только тогда, когда F частично рекурсивна.

Семейство называется вычислимым если существует по крайней мере одна вычислимая нумерация семейства .

Пусть - две нумерации одного и того же множества S. Говорят что нумерация сводится к нумерации , если существует такая что . Если сводится к , то символически изображаем это так .

Отношение , определенное на множестве H(S) всех нумераций множества S является транзитивным. Следовательно, отношение на H(S) является предпорядком.

Если и для , то эти нумерации эквивалентны и обозначаются . Класс нумераций эквивалентных нумерации обозначим через []. Множество классов эквивалентных нумераций обозначим через L(S).

На множестве H(S) можно задать операцию прямой суммы нумераций . Пусть нумерации , определим нумерацию следующим образом:

Основное свойство операции следующее:

Предложение 3

Пусть тогда сводится к тогда и только тогда когда сводится к и сводится к .

Обозначим через семейство всех вычислимых нумераций и через семейство классов эквивалентных вычислимых нумераций .

Делись добром ;)