Eфективні операції на функціях та множинах

(f)

В цьому випадку кажуть, що ОП z визначає ЧРО.

Тотальний ЧРО назвемо рекурсивним оператором (РО).

Інакше кажучи, ФО : Fm→Fn рекурсивний оператор, якщо

існує zN таке: для всіх fFm (f)=(Сn+1)-1(z(Сm+1(f))) (df1)

Дамо безпосереднє визначення РО, не використовуючи поняття оператора переліку. Вживатимемо скорочення для х1 , ..., хп.

ФО : Fm→Fn рекурсивний оператор, якщо

існує zN таке: для всіх fFm, ( , у)Nп+1 маємо

( , у)(f) и(f у= (и, )) (df2)

Зрозуміло, що таке визначення РО еквівалентне наступному:

існує ЧРФ така: для всіх fFm, ( , у)Nп+1 маємо

( , у)(f) и(f у=(и, )) (df3)

Теорема 11.1.2. Визначення df1, df2 та df3 еквівалентні.

Надалі для РО будемо, як правило, використовувати df3.

Теорема 11.1.3. Кожний РО є неперервним та монотонним.

Приклад 1. Нехай оператор : F1→F1 задається співвідношеням

Тоді немонотонний, отже, не РО.

Візьмемо скінченну f та нескінченну f. Тоді ()=f та (f)=f . Маємо f та (f)(). Отже, не є монотонним.

Приклад 2. Нехай оператор : F1→F1 задається співвідношеням

Тоді не неперервний і не РО.

Візьмемо функцію f із нескінченною Еf (наприклад, f тотожна функція). Тоді (f)=ff та ()=f для кожної скінченної f. Тому якщо (х, у)(f), то не існує скінченної функції f такої, що (х, у)(), бо ()=f. Отже, не є неперервним.

Для доведення рекурсивності операторів корисним є наступний критерій рекурсивності:

Теорема 11.1.4. Оператор : Fт→Fп є рекурсивним оператором неперервний та функція

є ЧРФ.

Розглянемо приклади використання теореми 11.1.4.