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

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, x1,..., xm), така, що для всiх z, x1, ..., xт, у1, ..., уп j(x1, ..., 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(x1, ..., xт, у1, ..., уп) iснує РФ s(x1, ..., xm) така, що для всiх x1, ..., xт, у1, ..., уп маємо f(x1, ..., xт, у1, ..., уп) = j(у1, ..., уп).

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

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

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

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

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

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

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

уÎDs(x) Û js(x)(у)¯ Û g(x, y)¯ Û jx(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)=js(x)(у). Зафіксуємо х. За побудовою функції f маємо Ds(x)=Еs(x). Тепер уÎЕs(x) Û уÎDs(x) Û js(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)=jt(x)(у). Зафіксуємо х. Mаємо уÎDt(x) Û jt(x)(у)¯ Û f(x, y)¯ Û уÎEx . Звідси Dt(x)=Ex .



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

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

Розглянемо функцію 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=2u+3v.

 

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

Приклад 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)= =js(x,y)(z). Зафіксуємо х та y. Маємо

zÎDs(x,y) Û js(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)=js(x,y)(z). Зафіксуємо х та y. За побудовою функції f маємо Ds(x,y)=Еs(x,y). Тепер

 

zÎЕs(x,y) Û zÎDs(x,y) Û js(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х значень x1, ..., xп маємо j = j .

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

j = j . (1)

 

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

‡агрузка...

 

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

 

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

 

j = j = j

 

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

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

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

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

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

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

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

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

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

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

Нехай f(x) - РФ. Тоді за тезою Чорча функція h(z, x)=jg(z)(x) є ЧРФ. За наслідком 2 існує nÎN таке, що для всiх x h(n, x)=jn(x), тобто для всiх x h(п, x) = jg(п)(x) = jn(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)=jn(x). Отже, jn(x) = h(n, x) = n для всiх x. Тому програма P із кодом n - шукана.

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

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

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

 

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

 

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

 

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

 

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

 

js(n(n)) (3)

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

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

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

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

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

- a(0)= , де m0 – дов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 та jn=jf(n).

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

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

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

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

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

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

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

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

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

 

jf(C(x,y))(z) = js(x,y)(z) для всiх x, y, zÎN . (1)

 

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

 

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

 

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

 

jg(C(a(y),y))(z)= jk(y)(z) для всiх y, zÎN . (3)

 

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

 


ЛЕКЦІЯ 11

 

ПЛАН

 

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

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

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

 

 

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

 

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

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

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

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

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

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

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

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

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

Cn(L)={Cn(x1, ..., xn) | (x1, ..., 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.041 сек.)