Нумерації. Теореми про нерухому точку, Детальна інформація

Зафiксуємо для кожного n(1 ефективну нумерацiю n-арних ЧРФ. Звичайно це буде нумерація на основі кодування МНР-програм (приклад 6), інколи нумерація на основі кодування МТ (приклад 8). Вказані нумерації назвемо стандартними нумераціями n-арних ЧРФ. Для стандартних нумерацій введемо наступні позначення.

. У випадку n=1 вживатимемо позначення Dm та Em.

Номер функцiї назвемо також iндексом функцiї. Номер функцiї в стандартній намерації назвемо стандартним iндексом функцiї.

Нумерація ( називається Гьодельовою, якщо існують рекурсивні функції f та g такі:

= (f(m);

.

Це означає, що існує пара алгоритмів, перший з яких за стандартним індексом функції знаходить її (-індекс, а другий за (-індексом функції знаходить її стандартний індекс.

Нехай F \xF02D деякий клас функцій вигляду Х\x2192Y, для якого задана нумерація (: N\x2192F. З кожною такою нумерацією ( зв’язана функція и: N*Х\x2192Y, що визначається умовою и(п, х) = (п(х). Таку функцію и називають спряженою з нумерацією (. Нумерація називається обчислюваною, якщо спряжена з нею функція є ЧРФ.

Для довiльного класу п-арних функцiй F клас всiх функцiй iз F фіксованої арності т будемо позначати Fт.

Функцiя и(y, x1, ..., xп) унiверсальна для класу Fп, якщо:

\xF02D для кожного значення m функцiя и(y, x1, ..., xп)\xF0CEFп;

\xF02D для кожної f\xF0CEFп iснує таке m, що f(x1, ..., xn)=и(т, x1, ..., xп) для всiх значень x1, ..., xп .

та замкнений вiдносно суперпозицiї. Нехай функцiя u унiверсальна для Tп. Тодi u(T.

Наслiдок 1. Функцiя, унiверсальна для класу n-арних РФ, не є ЧРФ.

Наслiдок 2. Функцiя, унiверсальна для класу n-арних ПРФ, не є ПРФ.

Теорема 3.2. Існує РФ, унiверсальна для класу n-арних ПРФ.

Наслiдок 1. Існує РФ, яка не є ПРФ.

Наслiдок 2. Для вiдповiдних класiв функцiй маємо строгi включення ПРФ(РФ(ЧРФ.

Теорема 3.3. Існує ЧРФ, унiверсальна для класу n-арних ЧРФ.

(x1, ..., xп).

МНР-програма, яка обчислює унiверсальну ЧРФ, називається унiверсальною МНР-програмою.

.

Машина Тьюрiнга, яка обчислює унiверсальну ЧРФ, називається унiверсальною МТ. Таку МТ, здатну моделювати роботу довiльної МТ за її кодом, теж можна задати в явному виглядi.

, що обчислює цей iндекс:

(у1, ..., уп).

вiд n можна зняти, якщо для завдання ЧРФ використати МТ.

, причому k \xF02D\xF020код МТ M, \xF02D не залежить вiд n .

(у1, ..., уп).

При т=п=1 спрощена s-m-n-теорема формулюється так:

Теорема 3.6. Для кожної ЧРФ f(x, y) iснує РФ s(x) така, що для всiх значень x, y маємо f(x, y)= (s(x)(y).