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

И если , то

2. С каждой тройкой объектов R связано отображение : так что для A, B, C, D ObR, если Mor (A, B), Mor (B, C), Mor (C, D), то

3. Для каждого А ObR в Mor (A, A) выделен элемент такой что для любого BObR, любого выполняются равенства

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 Скачать реферат