 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Еквівалентні визначення РПМ
Використовуючи множини-згортки, дамо еквiвалентнi визначення РМ, ПРМ та РПМ, заданих на Nn .
Тeорeма 1. Множина L Í Nn рекурсивна (примiтивно рекурсивна, рекурсивно перелiчна) Û множина Cn (L) рекурсивна (примiтивно рекурсивна, рекурсивно перелiчна)
Доводимо для випадку РМ (для ПРМ аналогiчно).
Нехай L Í N є РМ, тобто c L (x 1,..., xn) є РФ. Тодi
c L (Cn 1(x),..., Cnn (x)) = 
.
Справдi, x Î Cn (L) Û x = Cn (x 1,..., xn) для деякої n -ки
(x 1,..., xn)Î L Û (Cn 1(x),..., Cnn (x))Î L.
Отже, Cn (L) рекурсивна.
Нехай тепер Cn (L) є РМ, тобто 
- PФ. Тодi
(Cn (x 1,..., xn)) = c L (x 1,..., xn),
звiдки L є РМ.
Доводимо для випадку РПМ.
Нехай L Í Nn є РПМ, тобто L ={(g 1(x),..., gn (x)) | x Î N }для деяких РФ g 1,..., gn. Тодi Cn (L)={ Cn (g 1(x),..., gn (x)) | x Î N } - РПМ, бо Cn (g 1(x),..., gn (x)) є РФ.
Нехай тепер Cn (L) є РПМ, тобто Cn (L) = { g (x) | x Î N } для деякої РФ g. Тодi множина L ={(Cn 1(g (x)),..., Cnn (g (x))) | x Î N } є РПМ, бо Cn 1(g (x)),..., Cnn (g (x)) - РФ.
Ураховуючи теорему 1, обмежимося розглядом рекурсивних, примiтивно рекурсивних та рекурсивно перелiчних множин на N.
Співвідношення між класами ПРМ, РМ і РПМ установлює
Тeорeма 2. 1) кожна скiнченна множина є ПРМ;
2) кожна рекурсивна множина є РПМ;
3) клас ПРМ строго включається в клас РМ.
1) Нехай множина L ={ а 1,..., аn }. Тодi c L (x)= nsg(
) - ПРФ.
2) Нехай L Í N є РМ. Якщо L =Æ, то L за визначенням є РПМ. Якщо L ¹Æ, то зафiксуємо якийсь елемент b Î L. Функцiя c L рекурсивна, тому f(x) = x × c L (x)+ b × nsg (c L (x)) теж рекурсивна, причому L = Ef. Отже, L є РПМ c L (x 1,..., xn).
3) Кожна ПРФ рекурсивна, тому кожна ПРМ є РМ. Нехай u (t, x) - рекурсивна унiверсальна функцiя для ПРФ 1. Тодi f (x)= nsg (u (x, x)) є характеристичною функцiєю деякої РМ L. Якщо f (x) є ПРФ, то за унiверсальнiстю u (t, x) iснує k Î N таке, що f (x)= u (k, x) для всiх x. Тодi f (k)= u (k, k)= nsg (u (k, k)). Маємо суперечнiсть, тому f (x) не є ПРФ, звiдки L не є ПРМ.
Тeорeма 3. Класи ПРМ та РМ замкненi вiдносно операцiй È, Ç і доповнення.
Маємо c A È B (x)=s g (c A (x)+c B (x)), c A Ç B (x)= c A (x) × c B (x) та 
= nsg (c A (x)). Тому якщо c A і c B - РФ (ПРФ), то c A È B, c A Ç B та 
теж РФ (ПРФ).
Тeорeма 4. Множина L є нескінченною РМ Û L = Ef для деякої строго монотонної РФ f.
Для строго монотонних функцiй для всiх x Î D f виконується умова f(x) ³ x. Тому маємо 
. Якщо f рекурсивна, то 
теж рекурсивна, звiдки множина Ef рекурсивна.
Нехай L є нескінченною РМ. Задамо функцію f такою схемою примітивної рекурсії:
f (0)=m k (c L (k)=1);
f (х +1)=m k (c L (k)=1 та k>f (x)).
За побудовою L = Ef та f строго монотонна. В силу нескінченності множини L функція f тотальна. Отже, f - строго монотонна РФ.
Тeорeма 5. Нехай L - нескiнченна РПМ. Тодi iснує нескiнченна рекурсивна множина M, така, що MÍL.
Нехай L - нескiнченна РПМ. Тодi L = Eg для деякої РФ g. Розглянемо функцiю f, задану такою схемою примiтивної рекурсiї:
f (0)= g (0);
f (x +1)= g (m k (g (k)> f (x)).
За побудовою функцiя f строго монотонна, причому f тотальна через нескiнченність Eg . Отже, f - строго монотонна рекурсивна функцiя, тому Ef - нескiнченна РМ. Зрозумiло, що Ef Í Eg = L, тому множина Ef - це шукана множина M.
Тeорeма 6. Нехай L - нескiнченна РПМ. Тодi iснує iн’єктивна РФ f така, що L = Ef .
Маємо L = Eg для деякої РФ g. Розглянемо функцiю f, задану такою схемою примiтивної рекурсiї:
f (0)= g (0);
f (x +1)= g (m k (g (k)¹ f (0), …, g (k)¹ f (x))) = 
Через нескiнченність Eg функцiя f iн’єктивна i тотальна, причому
Ef = Eg = L. Отже, f - шукана iн’єктивна РФ.
Тeорeма 7. Існує РФ a така, що для кожного х Î N E a( x ) =Dx, причому ja( x ) є РФ при Dx ¹Æ.
Зафіксуємо довільне х Î N. Задамо ефективний процес поетапного породження множини Dx, формуючи список елементів Dx із повторами. Виконання одної команди МНР-програми (МТ) при обчисленні певної ЧРФ назвемо кроком обчислення.
Етап 1. Робимо 1-ий крок обчислення j x (0); якщо j x (0) обчислене, заносимо 0 до списку.
Етап п +1. Робимо по п +1 кроків обчислення для j x (0), j x (1), …, j x (п); усі такі k £ n, для яких j x (k) обчислене, заносимо до списку.
Задамо функцію f (x, y) наступним чином. Для кожного фіксованого х Î N покладемо:
f (x, 0) є 1-м елементом списку;
f (x, у +1)= = 
За тезою Чорча так задана f (x, y) є ЧРФ. Тому за s-m-n- теоремою існує така РФ a(x), що f (x, y)=ja( x )(y)для всіх значень x, y. За побудовою E a( x ) =Dx. Якщо Dx =Æ, то ja( x )= f Æ. Якщо Dx ¹Æ, то при такому фіксованому х функція f (x, y) визначена для всіх у Î N, тому ja( x ) тотальна, отже, функція ja( x ) є РФ.
Тeорeма 8. Існують РФ s і t такі, що для кожного х Î N E s( x ) =Dx та Dt ( x ) =Ex.
Задамо функцію f (x, у) = m z (Px (z)¯ y) = 
За ТЧ f (x, у) є ЧРФ. Тому за s-m-n- теоремою існує така РФ t (x), що f (x, y)=j t ( x )(y)для всіх значень x, y. Тоді у Î Ex Û f (x, у) визначене Û j t ( x )(y)визначене Û у Î Dt ( x ). Звідси Dt ( x ) =Ex.
Задамо функцію g (x, у) = 
За ТЧ g (x, у) є ЧРФ. Тому за s-m-n- теоремою існує така РФ s (x), що g (x, y)=j s ( x )(y)для всіх значень x, y. За побудовою E s( x ) = D s( x ) . Маємо у Î Dx Û f (x, у) визначене Û j s ( x )(y)визначене Û у Î D s( x ) Û у Î E s( x ) . Звідси Dx= E s( x ) .
Тeорeма 9. Існує РФ b така, що для кожного х Î N E b( x ) =Еx, причому jb( x ) є РФ при Еx ¹Æ.
Узявши функції a і t із тeорeми 7 та тeорeми 8, для кожного х Î N маємо Dt ( x ) =Ex і E a( x ) =Dx, причому ja( x )є РФ при Dx ¹Æ. Тоді E a( t ( x )) =Dt ( x ) =Ex для кожного х Î N, причому ja( t ( x ))є РФ при Dt ( x ) =Ex ¹Æ. Тому РФ b(x)=a(t (x)) шукана.
Тeорeма 10. Наступнi визначення РПМ еквiвалентнi:
df1) L= Æ або L є областю значень деякої РФ;
df2) L є областю значень деякої ЧРФ;
df3) L є областю визначення деякої ЧРФ;
df4) часткова характеристична функцiя множини L є ЧРФ.
Iмплiкацiї df1 Þdf2 та df4 Þdf3 є очевидними.
Покажемо df3 Þdf1. Нехай множина L є областю визначення деякої ЧРФ, нехай х - індекс такої ЧРФ, тобто L = Dx. Візьмемо РФ a(x) із тeорeми 7, тоді E a( x ) =Dx, причому ja( x )є РФ при Dx ¹Æ. Отже, або Dx =Æ, або Dx=E a( x ) і ja( x )є РФ.
Аналогічно, використовуючи теорему 9, показуємо df2 Þdf1.
Твердження df2 Ûdf3 випливає із теореми 8. Залишається показати df3 Þdf4. Нехай L = Df для деякої ЧРФ f. Тоді маємо 
s (o (f (x))).
Зауважимо, що df3 та df4 можна без зміни використовувати для РПМ, заданих на Nn.
Поиск по сайту: