Теория нумераций (стр. 2 из 22)

Пусть

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

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

.

Нумерация

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

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

Нумерация

, , вычислима тогда и только тогда, когда нумерация

свертки семейства , определенная так

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

n‑развертки семейства определенная так

является вычислимой.

Обозначим через

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

Пусть

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

является вычислимой.

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

Нумерация

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

Функция

, связанная с нумерацией

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

Всякая универсальная функция F для семейства

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

Семейство

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

Пусть

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

Отношение

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

Если

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

На множестве H( S ) можно задать операцию прямой суммы нумераций

. Пусть нумерации , определим нумерацию следующим образом:

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

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

Пусть

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

Обозначим через

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

Главные нумерации

Рассмотрим понятие главной нумерации для семейства рекурсивно перечислимых множеств. Это понятие позволяет ответить (в случае семейства рекурсивно перечислимых множеств) на вопрос: «какую нумерацию данного множества следует считать наиболее естественной?»

Нумерацию

назовем главной, если любая нумерация сводится к .