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

для х1 , ..., хп.

ФО (: Fm\x2192Fn \xF02D\xF020рекурсивний оператор, якщо

, у)(Nп+1 маємо

)) (df2)

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

, у)(Nп+1 маємо

)) (df3)

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

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

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

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

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

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

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

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

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

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

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

є ЧРФ.

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

Приклад 3. Оператор (: Fт\x2192Fп задається умовою ((f)=g для всіх f(Fт, де g \xF02D\xF020фіксована ЧРФ. Тоді ( є РО.

є ЧРФ за ТЧ.

Приклад 4. Задамо оператор (: F1\x2192F1 таким співвідношенням: ((f)(x)= f(f(x+2))+5x для всіх f(F1. Тоді ( є РО.

Оператор ( неперервний: (х, у)(((f) ( (х, у)(((() виконується для кожної скінченної ((f такої, що x+2(D( та f(x+2)(D(. Тепер



є ЧРФ за ТЧ.

, у)=0) для всіх f(Fп+1. Тоді М є РО.

) для кожної такої ((f. Тепер функція

є ЧРФ за ТЧ.

Приклад 6. Нехай ФО (0 : F1\x2192F1 задається співвідношенням (0({(0,0)})={(0,0)} та (0({(1,0)})={(0,1)}; для інших f(F1 значення (0(f) невизначене. Тоді (0 розширюється до ЧРО та не розширюється до жодного РО.