Воспользуйтесь поиском к примеру Реферат        Грубый поиск Точный поиск
Вхід в абонемент


Интернет реклама УБС






Реферат на тему:

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

Множество всех n-арных функций на N, то есть функций с Nп в N, обозначим Fп. Объединение множеств Fп для всех п1 обозначим F. Множество всех полных функций по Fп и множество всех тотальных функций с F соответственно обозначим Tп и T. Cкинченни множества в этом разделе обозначаем F, конечные функции обозначаем.

произвольную функцию вида: (2N) m> 2N назовем m-арным множественным оператором (сокращенно МО).

произвольную функцию вида Ш: (F) m> F назовем m-арным функциональным оператором (сокращенно ФЛ).

Функциональные операторы называют также операциями на функциях, или композициями.

Пример. Операции суперпозиции Sn +1 (F) m> F, примитивной рекурсии R: FF> F и минимизации M: FF> F являются примерами ФО.

МО (2N) m> 2N называется монотонным, если из условия А1В1, А2 В2, ..., Ат Вт следует (А1, ..., Ап) (В1, ..., Вп).

ФЛ (F) m> F называется монотонным, если из условия f1 g1, f2 g2, ..., fт GТ следует (f1, ..., fп) (g1, ..., gп). < /p>

МО (2N) m> 2N называется непрерывным, если для всех х n, A (2N) m имеем х (A) FA: х (F).

ФЛ: Fп> F называется непрерывным, если для всех хNп, yN и fFп имеем (х, у) (f) f (х, у) ().

Легко доказать, что каждый непрерывный оператор является монотонным.

11.1. ОПЕРАТОРЫ ПЕРЕЧНЯ. ЧАСТИЧНО рекурсивно И рекурсивно ОПЕРАТОРЫ

Эффективность множественного оператора: 2N> 2N означает воз-можность эффективно задать множество (A), если эффективно задается множество А. Эффективные множественные операторы называются [10] операторами перечня (сокращенно ОП).

Для каждого zN оператор перечня z: 2N> 2N задается соотношением z (A) = {x | u (Fu А C (x, u) Dz)}.

Иначе говоря, xz (A) u (Fu А C (x, u) Dz).

Теорема 11.1.1. Каждый оператор перечне есть непрерывным и монотонным.

Множество АN однозначна, если С -1 (А) = {(l (x), r (x))} является функциональным отношением. Понятно, что A однозначнa (Сm +1) -1 (A) является функциональным отношением для каждого m1. Следовательно, множество A однозначнa m1 fFm: A = Сm +1 (f). Поэтому для множества всех однозначных множеств можно ввести следующее обозначение:

CF = {С (f) | fF1} = {Сm +1 (f) | fFm}.

Каждый функциональный оператор: Fm> Fn задает множественный оператор: CF> CF и наоборот:

: Fm> Fn

Сm +1 (Сm +1) -1 Сn +1 (Сn +1) -1

: CF> CF

Отсюда (f) = (Сn +1) -1 ((Сm +1 (f))) и (A) = Сn +1 (((Сm +1) -1 (A))).

ФЛ: Fm> Fn называется частично рекурсивным оператором (ЧРО), если существует zN такое, что для всех fFm имеем:

(f) =

В этом случае говорят, что ОП z определяет ЧРО.

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

Иначе говоря, ФЛ: Fm> Fn? рекурсивный оператор, если

существует zN следующее: для всех fFm (f) = (Сn +1) -1 (z (Сm +1 (f))) (df1)

Дадим непосредственное определение РО, не используя понятие оператора перечня. Употреблять сокращение для х1, ..., хп.

ФЛ: Fm> Fn? рекурсивный оператор, если

существует zN следующее: для всех fFm (, в) Nп +1 имеем

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

Понятно, что такое определение РО эквивалентно следующем:

существует ЧРФ такая: для всех fFm (, в) 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.

Пример 3. Оператор: Fт> Fп задается условием (f) = g для всех fFт, где g? Фиксированная ЧРФ. Тогда есть РО.

Оператор непрерывный: условие (, у) (f) (, у) () выполняется для произвольной конечной f, ведь (f) = () = g. Функция (и,) = является ЧРФ по ТЧ.

Пример 4. Зададим оператор: F1> F1 следующим соотношением: (f) (x) = f (f (x +2)) +5 x для всех fF1. Тогда есть РО.

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

(и, х) =

является ЧРФ по ТЧ.

Пример 5. Оператор минимизации М: Fп +1> Fп задается условием М (f) () = у (f (, у) = 0) для всех fFп +1. Тогда М является РО.

Оператор М непрерывный: у = у (f (, у) = 0) у = у ((, у) = 0) выполняется для каждой f такой, что (0), (1), ... (, в) D, ибо y = М (f) () y = М () () для каждой такой f. Теперь функция

(и,) = является ЧРФ по ТЧ.

Пример 6. Пусть ФЛ 0: F1> F1 задается соотношением 0 ({(0,0)}) = {(0,0)} и 0 ({(1,0)}) = {(0,1)}, для других fF1 значение 0 (f) неопределенное. Тогда 0 расширяется до ЧРО но не расширяется к одному РО.

Поскольку {C (0,0)} = {0} = F1 и {C (1,0)} = {2} = F4, берем z такое, что Dz = {C (0,20), C (1,22)}. Пусть ОП z задается таким Dz, т.е. xz (A) u (Fu А C (x, u) Dz). Понятно, что для


Страницы: 1 2 3