Нумерації. Теореми про нерухому точку

З визначення випливає, що (x, y) є ПРФ.

Теорема 1.2 (про основну властивість функції Гьоделя). Для довiльної скiнченної послiдовностi натуральних чисел b0, b1, ..,bn існує натуральне число t таке, що (t, i)=bi для всiх i{0,...,n}.Використання функції Гьоделя дає змогу промоделювати опера-цiю примiтивної рекурсiї операціями суперпозиції та мінімізації:

Теорема 1.3. Функцiя f=R(g, h) може бути отримана iз функцiй g, h, базових функцiй і функцiй +, за допомогою скiнченної кiлькостi застосувань операцiй Sn+1 та М.

Наслiдок. Клас ЧРФ спiвпадає з класом функцiй, отриманих із функцій о, s, I , +,за допомогою операцiй Sn+1 та M.

2. ЕФЕКТИВНІ НУМЕРАЦІЇ ФОРМАЛЬНИХ МОДЕЛЕЙ АЛГОРИТМІВ ТА АОФ

Розглянемо приклади ефективних нумерацій формальних моделей алгоритмів та алгоритмічно обчислюваних функцій.

Приклад 1. Однозначну ефективну нумерацiю всiх МНР-програм задамо на основi кодування МНР-програм як скiнченних послiдов-ностей команд МНР. Кодування команд задамо так:

Зрозумiло, що бiєктивне вiдображення множини всiх команд МНР на N. Використовуючи розглянуту вище бiєкцiю : →N, задамо кодування всiх МНР-програм так.

Якщо P МНР-програма I1I2...Iк , то (P) = ((I1),..., (Ik)).

Приклад 2. Ефективну нумерацiю всiх МТ задамо на основi кодування МТ. Кожну МТ можна задати послiдовнiстю її команд такою, що 1-а команда мiстить в лiвiй частинi символ q0 , остання команда мiстить в правiй частинi символ q*. Таке завдання неоднозначне, бо множину команд МТ можна впорядкувати у виглядi послiдовностi з вищевказаною властивiстю багатьма способами. Тому наша нумерацiя МТ неоднозначна.

Занумеруємо внутрiшнi стани МТ та символи стрiчки. Нехай Q={q1,..., qf}, T={a1,..., am}. Кодування команд МТ задамо так:

Таке є бiєктивним вiдображенням множини всiх можливих команд машин Тьюрiнга на N. Використовуючи розглянуту вище бiєкцiю : →N, визначимо код МТ M, заданої послiдовнiстю команд I1I2...Iк , таким чином: (M) ((I1),..., (Ik)). Але та бiєктивнi, тому теж бiєкцiя. Тодi 1 шукана однозначна нумерацiя послiдовностей команд МТ, але неоднозначна нумерацiя всiх МТ. Неважко переконатись, що така нумерацiя ефективна.

Приклад 2.1. Знайдемо код МТ М, яка обчислює бінарну функцію х+у. Вважаємо a0=, a1=|, a2=# та q*=q2 . Використаємо приклад 1 розділу 2.2. Маємо:

Число nN вважаємо номером ЧРФ f, якщо n є кодом якогось ОТ, i значенням цього ОТ є функцiя f. Числа, якi не є кодами ОТ, та коди тих ОТ, якi не задають ЧРФ, вважаємо номерами всюди невизначеної функцiї f. Зрозумiло, що за кожною ЧРФ можна ефективно знайти її номер. З iншого боку, за кожним nN ефективно визначається ЧРФ f така, що (n)=f : за n як за кодом будуємо ОТ; якщо ОТ з таким кодом iснує та задає ЧРФ, то (n) саме така ЧРФ f ; якщо ОТ з таким кодом iснує, але не задає ЧРФ, то (n)=f ; якщо ОТ з таким кодом не iснує, то (n)= f. Отже, є ефективною нумерацiєю всiх ЧРФ.

Приклад 3.1. Знайдемо код ОТ алгебри п-арних ЧРФ для всюди невизначеної функцiї f. Згадуючи приклад 9 розділу 6.6, для f маємо ОТ М(s), звідки (M(s)) = (s)+3 = 44+3=19.

Приклад 4. Ефективну нумерацiю всiх ПРФ задамо на основi кодування операторних термiв алгебри ПРФ. Така нумерацiя ПРФ неоднозначна. Кодування ОТ алгебри ПРФ задамо так

Число nN вважаємо номером ПРФ f, якщо n є кодом якогось ОТ та значенням цього ОТ є функцiя f. Числа, якi не є кодами ОТ, та коди тих ОТ, якi не задають ПРФ, вважаємо номерами функцiї о.