АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

S-M-N-теорема, приклади її використання

Читайте также:
  1. Аналіз використання виробничої потужності підприємства
  2. Аналіз використання матеріальних ресурсів
  3. Аналіз використання обладнання і виробничої потужності підприємства
  4. Аналіз використання технологічного обладнання
  5. Аналіз ефективності використання основних фондів
  6. Аналіз інтенсивності й ефективності використання основних засобів
  7. Аналіз показників використання основних засобів підприємства
  8. Аналітичний огляд використання вторинної сировини і відходів
  9. Баланс часу зміни та коефіцієнт використання часу зміни
  10. Будова, призначення та правила використання порошкових вогнегасників.
  11. Вартісні показники ефективності використання

 

Теорема 4 (s-m-n -теорема). Для довiльних m, n >1 iснує (m +1)- арна РФ s (z, x 1, ..., xm), така, що для всiх z, x 1, ..., xт, у 1 ,..., уп j (x 1 ,..., xт, у 1 ,..., уп) =j (у 1 ,..., уп).

Приклад 1. Залежнiсть функцiї s вiд n можна зняти, якщо для завдання ЧРФ використати МТ.

Справді, за z визначаємо МТ із кодом z для функцiї j . Задамо нову МТ M, яка злiва вiд початкового вмiсту стрiчки дописує слово , a далi моделює роботу МТ із кодом z. Така МТ M при входi обчислює n -арну функцiю j , причому k - код МТ M - не залежить вiд n.

Теорема 5 (s - m - n -теорема в спрощенiй формi). Для кожної ЧРФ f (x 1 ,..., xт, у 1 ,..., уп) iснує РФ s (x 1, ..., xm) така, що для всiх x 1, ..., xт, у 1 ,..., уп маємо f (x 1 ,..., xт, у 1 ,..., уп) = j (у 1 ,..., уп).

При т=п= 1 спрощена s - m - n -теорема формулюється так:

Теорема 6. Для кожної ЧРФ f (x, y) iснує РФ s (x) така, що для всiх значень x, y маємо f (x, y)= j s (x)(y).

Розглянемо приклади застосування s - m - n -теореми.

Приклад 2. Існує РФ s (x, y) така, що для всіх х, y, z Î N маємо j s ( x , y )(z)=j x (z)+j y (z).

Розглянемо функцію f (x, y, z) = j x (z) + j y (z). Функція f є ЧРФ, тому за s - m - n -теоремою існує РФ s (x, y) така, що для всіх х, y, z Î N маємо f (x, y, z)=j s ( x , y )(z)=j x (z)+j y (z).

Приклад 3. Для кожної 1-арної ЧРФ f існує РФ s (x), така, що для всіх х Î N маємо Ds ( x )= f -1(Dx).

Розглянемо функцію g (x, y) = j x (f (y)). Така функція є ЧРФ за ТЧ, тому за s - m - n -теоремою існує РФ s (x) така, що для всіх х, y Î N g (x, y) = j s ( x )(у). Зафіксуємо х. Mаємо

у Î Ds ( x ) Û j s ( x )(у)¯ Û g (x, y)¯ Û j x (f (y))¯ Û f (yDx Û y Î f -1(Dx).

Звідси Ds ( x )= f -1(Dx).

Приклад 4. Існує РФ s (x) така, що для всіх х Î N маємо Еs ( x )= Dx.

Розглянемо функцію f (x, y)= Така функція є ЧРФ за ТЧ, тому за s - m - n -теоремою існує РФ s (x) така, що для всіх х, y Î N маємо f (x, y)=j s ( x )(у). Зафіксуємо х. За побудовою функції f маємо Ds ( x )= Еs ( x ). Тепер у Î Еs ( x ) Û у Î Ds ( x ) Û j s ( x )(у)¯ Û f (x, y)¯ Û у Î Dx.

Звідси Еs ( x )= Dx.

Приклад 5. Існує РФ t (x) така, що для всіх х Î N маємо Dt ( x )= Еx.

Розглянемо функцію f (x, y)= Така функція є ЧРФ за ТЧ, тому за s - m - n -теоремою існує РФ t (x) така, що для всіх х, y Î N f (x, y)=j t ( x )(у). Зафіксуємо х. Mаємо у Î Dt ( x ) Û j t ( x )(у)¯ Û f (x, y)¯ Û у Î Ex. Звідси Dt ( x )= Ex.

Приклад 6. Існує РФ s (x) така, що для всіх х Î N маємо

={(u, v) | x =2 u +3 v }.

Розглянемо функцію f (x, u, v)=

За ТЧ f є ЧРФ, тому за s - m - n -теоремою існує РФ s (x) така: для всіх х, u, v Î N f (x, u, v)= (u, v). Зафіксуємо х. Тепер

 

(u, v Û (u, v)¯ Û f (x, u, v)¯ Û x =2 u +3 v.

 

Звідси ={(u, v) | x =2 u +3 v }.

Приклад 7. Існує РФ s (x, y) така, що для всіх х, y Î N маємо Ds ( x , y )= Dx È Dy.

Розглянемо функцію f (x, y, z)= Така функція є ЧРФ за ТЧ, тому за s - m - n -теоремою існує РФ s (x, y) така, що для всіх х, y, z Î N маємо f (x, y, z)= =j s ( x , y )(z). Зафіксуємо х та y. Маємо

z Î Ds ( x , y ) Û j s ( x , y )(z)¯ Û f (x, y, z)¯ Û z Î Dx È Dy.

 

Звідси випливає Ds ( x , y )= Dx È Dy.

Приклад 8. Існує РФ s (x, y) така, що для всіх х, y Î N маємо Ds ( x , y )= Еs ( x , y )= Dx Ç Dy.

Розглянемо функцію f (x, y, z)= Така функція є ЧРФ за ТЧ, тому за s - m - n -теоремою існує РФ s (x, y) така, що для всіх х, y, z Î N маємо f (x, y, z)=j s ( x , y )(z). Зафіксуємо х та y. За побудовою функції f маємо Ds ( x , y )= Еs ( x , y ). Тепер

 

z Î Еs ( x , y ) Û z Î Ds ( x , y ) Û j s ( x , y )(z)¯ Û f (x, y, z)¯ Û z Î Dx Ç Dy.

 

Звідси отримуємо Ds ( x , y )= Еs ( x , y )= Dx Ç Dy.

 


ЛЕКЦІЯ 10

 

ПЛАН

 

1. Теореми Кліні про нерухому точку.

 

1. Теореми Кліні про нерухому точку

 

Теорема 1. Нехай f - (n +1)- арна РФ. Тодi iснує n-арна РФ g, така, що для всiх значень x 1,..., xп маємо j = j .

За s - m - n -теоремою iснує РФ s (и, x 1, ..., xп) така, що для всiх u, x 1,..., xп, y маємо

j = j . (1)

 

Нехай функцiя f (s(x 1,..., xп), x 1,..., xп) має iндекс k у нумерацiї (n +1)-арних ЧРФ, тобто це функцiя j ( u, x 1,..., xп). За тотальнiстю функцiй f та s функцiя j тотальна. Тому при u = k для всiх x 1,..., xп маємо

 

f (s(x 1,..., xп), x 1,..., xп) = j (k, x 1,..., xп). (2)

 

Iз (1) при u = k та iз (2) дiстаємо

 

j = j = j

 

для всiх x 1,..., xп . Отже, функцiя g (x 1,..., xп)= s (k, x 1,..., xп) - шукана РФ.

Для випадку n =0 теорема 1 переформульовується так:

Теорема 2. Нехай f (x) - РФ. Тодi iснує n Î N таке, що j n = j f (n).

Наведену теорему Клiнi про нерухому точку краще називати теоремою про псевдонерухому точку. Справдi, умова j n= j f (n) зовсiм не означає, що n = f (n), a свiдчить тiльки про те, що n i f (n) - iндекси одної i тої ж ЧРФ.

Теорему про нерухому точку називають також теоремою про рекурсiю, бо вона виражає рекурсивне визначення дуже загального вигляду. Наприклад, визначимо функцiю j n через задану РФ f так: j n= j f (n) . Тодi j n ефективно визначена через n - код МНР-програми для її обчислення, бо таке n iснує згiдно з теоремою 2.

Наслiдок 1. Нехай f (x) - РФ. Тодi iснує n Î N таке, що Dn = Df(n) та En = Ef(n).

Справдi, згiдно з теоремою 2 досить узяти n Î N таке, що j n = j f(n).

Наслiдок 2. Нехай h (z, x) - ЧРФ. Тодi iснує n Î N таке, що для всiх x h (n, x) = j n (x).

За s - m - n -теоремою iснує РФ s (z) така, що h (z, x) = j s (z)(x) для всiх z, x. За теоремою 2 iснує таке n, що j n = j s(n) , тобто h (n, x) = j s(n) (x) = j n (x)для всiх x.

Зауважимо, що формулювання наслідку 2 - це первісне формулювання самого С.Кліні теореми про нерухому точку. Покажемо, що наслідок 2 та теорема 2 еквівалентні. Для цього виведемо теорему 2 із наслідку 2.

Нехай f (x) - РФ. Тоді за тезою Чорча функція h (z, x)=j g(z) (x) є ЧРФ. За наслідком 2 існує n Î N таке, що для всiх x h (n, x) = j n (x), тобто для всiх x h (п, x) = j g(п) (x) = j n (x).

МНР-програма P самотворна, якщо для довiльного x Î N маємо P (x)¯t(P), де t(P) - код програми P. На перший погляд, таких програм бути не може, бо для побудови P треба знати t(P), тобто саму програму P. Проте самотворнi програми таки iснують!

Теорема 3. Існує МНР-програма P така, що P (x)¯t(P) для всiх значень x.

Вiзьмемо функцiю h (z, x) = z. За наслiдком 2 iснує таке n, що для всiх x h (n, x) = j n (x). Отже, j n (x) = h (n, x) = n для всiх x. Тому програма P із кодом n - шукана.

Покажемо тепер, що нерухома точка кожної РФ j n ефективно залежить вiд її iндексу n. Це посилює твердження теореми 2.

Теорема 4. Існує РФ a(x) така: для кожного n Î N, якщо j n є РФ, то ja(n) = .

За s - m - n -теоремою iснує РФ s (x) така, що

 

= j s (x)(y)для всiх x, y Î N. (1)

 

Тодi за s - m - n -теоремою iснує РФ n (x), для якої

 

j n (s (x)) = j n (n)(x) для всiх n, x Î N. (2)

 

Якщо j n є РФ, то кожне значення j n (x) визначене. Взявши x = n (n), iз (1) маємо

 

j s ( n (n)) (3)

та iз (2) маємо j n (s (n (n))) = j n (n)(n (n)). Звiдси та із (3) дiстаємо j s ( n (n))= . Поклавши a(x)= s (n (x)), маємо ja(n) = .

Покажемо, що для кожної РФ можна ефективно знайти монотонно зростаючу послiдовнiсть її нерухомих точок. Звiдси, зокрема, випливає нескiнченнiсть множини нерухомих точок кожної РФ.

Теорема 5. Для кожної РФ f (x) iснує строго монотонна РФ a(x), така, що для кожного n Î N маємо ja(n)=j f (a(n)).

За s - m - n -теоремою iснує РФ s (x) така: j s (x)(y)для всiх x, y Î N. Нехай m - деякий iндекс функцiї s (x), тобто s (x) – суть j m (x). Звiдси для всiх y Î N, тобто j m (m) - нерухома точка функцiї f. Згiдно із зауваженням 1 до s - m - n -теореми s (xx для всiх x Î N, тому j m (mm.

Функцiю a(x) задамо так:

- a(0)= , де m 0 – довiльний iндекс функцiї s;

- a(k +1)= , де mk+ 1 - такий iндекс функцiї s, що mk+ 1>a(k)

(у силу твердження 1 такий iндекс знаходиться ефективно).

Кожне значення функцiї a є нерухомою точкою функцiї f. Функцiя a алгоритмiчно обчислювана, вона тотальна в силу тотальностi функцiї s. За ТЧ a є РФ, причому для всiх k Î N a(k +1)= ³ mk+ 1>a(k). Тому a - строго монотонна РФ.

Наслiдок. Для кожних РФ f (x) та k Î N iснує n Î N таке, що n>k та j n =j f (n).

Розглянутi нами ефективнi нумерацiї ЧРФ неоднозначнi. Однозначнi ефективні нумерацiї ЧРФ iснують, але немає в певному смислi "природних" однозначних ефективних нумерацiй ЧРФ.

Теорема 6. Нехай f (x) - строго монотонна тотальна функцiя, для якої виконуються умови:

1) якщо m ¹ n, то j f (т)¹j f (n);2) f (n) - найменший iндекс функцiї j f (n) .

Тодi функцiя f не є ЧРФ.

Функцiя f не може бути тотожною, бо тодi з умови m ¹ n випливає j m ¹j n . Тому iснує таке k Î N, що f (n)> n при n ³ k. Але f (n)- найменший iндекс функцiї j f (n) , тому j f (т) ¹ j f (n) для всіх n ³ k. Якщо f рекурсивна, то за наслiдком теореми 5 iснує n Î N таке, що n > k і j f (n)=j n . Дiстали суперечнiсть, тому функцiя f не є РФ та не є ЧРФ.

Спiльної нерухомої точки для двох довiльних РФ може не бути. Нехай a і b - рiзнi РФ, нехай k і m - iндекси функцiй a і b, тобто a=j k та b=j m . Вiзьмемо функцiї-константи f (x)= k і g (x)= m. Якщо iснує спiльна нерухома точка n для f і g, то j n = j f (n) та j n = j g (n). Звiдси a=j k =j f (n)=j n =j g (n)= j m = b, що суперечить припущенню a ¹ b.

Проте можна знайти пару ефективно зв’язаних нерухомих точок для пари заданих РФ:

Теорема 7 (про парну рeкурсiю). Для кожної пари РФ f (x) і g (x) iснують m, n Î N такi, що j m = j f (C (m,n)) та j n = j g (C (m,n)) .

За s - m - n -теоремою iснує РФ s (x, y) така:

 

j f (C (x,y))(z) = j s (x,y)(z) для всiх x, y, z Î N. (1)

 

За теоремою 1 для РФ s (x, y) iснує РФ a(y) така, що ja(y) = j s (a(y) ,y) для всiх y Î N. Ураховуючи (1), звiдси маємо:

 

ja(y) = j f (C (a(y) ,y)) для всiх y Î N. (2)

 

За s - m - n -теоремою iснує РФ k (y) така:

 

j g (C (a(y) ,y))(z)= j k (y)(z) для всiх y, z Î N. (3)

 

За теоремою 2 для РФ k (y) iснує n Î N таке, що jn = j k(n). Звiдси, враховуючи (3), маємо j n = j g (C (a( п ), п )). Покладемо m =a(n). Тодi з j n = =j g (C (a(п) ,п)) при y = n дістаємо j n = j g (C (т,п)) та з (2) при y = n маємо j т =ja(т) = j f (C (a(п) ,п)) = j f (C (т,п)) .

 


ЛЕКЦІЯ 11

 

ПЛАН

 

1. Поняття примітивно рекурсивної, рекурсивної та рекурсивно перелічної множини (ПРМ, РМ і РПМ).

2. Еквівалентні визначення РПМ.

3. Властивості ПРМ, РМ та РПМ.

 

 

1. Поняття примітивно рекурсивної, рекурсивної і рекурсивно перелічної множини (ПРМ, РМ та РПМ)

 

Множину M Í Nn називають рекурсивною (скорочено РМ), якщо її характеристична функцiя c M рекурсивна.

Множину M Í Nn називають примiтивно рекурсивною (скорочено ПРМ), якщо її характеристична функцiя c M примiтивно рекурсивна.

Зрозумiло, що кожна ПРМ є рекурсивною множиною.

Множину M Í N називають рекурсивно перелiчною (скорочено РПМ), якщо M =Æ або M = Ef для деякої рекурсивної функцiї f.

Множину M Í Nn називають РПМ, якщо M =Æ або iснують 1-арнi РФ g 1,..., gn такi, що M ={(g 1(x),..., gn (x)) | x Î N }.

Як наслiдки тези Чорча дiстаємо такi твердження:

- клас РМ збігається з класом алгоритмiчно розв’язних множин натуральних чисел;

- клас РПМ збігається з класом алгоритмiчно перелiчних множин натуральних чисел.

Для кожної L Í Nn визначимо множину-згортку

Cn (L)={ Cn (x 1,..., xn) | (x 1,..., xnL }.

Нехай L Í Nn та M Í Nn. Безпосередньо iз визначень випливає:

Cn (L È M)= Cn (LCn (М), Cn (L Ç M)= Cn (LCn (М), Cn (Nn \ L)= N \ Cn (L).

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.027 сек.)