WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Нумерації. Теореми про нерухому точку - Реферат

Нумерації. Теореми про нерухому точку - Реферат

Теорема 3.1. Нехай T  деякий клас тотальних п-арних функцiй наN, який мiститьфункцiїо, s, Iта замкнений вiдносно суперпозицiї. Нехай функцiяuунiверсальна для Tп. Тодi uT.

Наслiдок 1.Функцiя, унiверсальна для класу n-арних РФ, не є ЧРФ.

Наслiдок 2.Функцiя, унiверсальна для класу n-арних ПРФ, не є ПРФ.

Теорема 3.2.Існує РФ, унiверсальна для класу n-арних ПРФ.

Наслiдок 1. Існує РФ, яка не є ПРФ.

Наслiдок 2.Для вiдповiдних класiв функцiй маємо строгi включенняПРФРФЧРФ.

Теорема 3.3. Існує ЧРФ, унiверсальна для класу n-арних ЧРФ.

Такою буде функція и(у, x1, ..., xп) = (x1, ..., xп).

МНР-програма, яка обчислює унiверсальну ЧРФ, називається унiверсальною МНР-програмою.

Унiверсальна програма декодує довiльне число y в програму Py , а далi вона моделює роботу Py . Тому така унiверсальна програма може бути задана в явному виглядi. Отже, можна конструктивно знайти iндекс k унiверсальної функцiї u в стандартній нумерацiї (n+1)-арних ЧРФ, тобто u суть функцiя .

Машина Тьюрiнга, яка обчислює унiверсальну ЧРФ, називається унiверсальною МТ. Таку МТ, здатну моделювати роботу довiльної МТ за її кодом, теж можна задати в явному виглядi.

Для кожного фiксованого значення а1, ..., ат аргументiв x1, ..., xт (m+n)-арна ЧРФ (x1, ..., xт, у1, ..., уп). стає n-арною ЧРФ (у1, ..., уп). Її iндекс k можна ефективно знайти за z та а1, ..., ат . Це означає, що iснує (m+1)-арна РФ, яку традицiйно позначають s, що обчислює цей iндекс:

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

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

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

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

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

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

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

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

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

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

Розглянемо функцію g(x, y)=x(f(y)). Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s(x) така, що для всіх х, yN маємо g(x, y)=s(x)(у). Зафіксуємо х. Mаємо уDs(x)  s(x)(у) g(x, y)  x(f(y))  f(y)Dx yf-1(Dx). Звідси Ds(x)= f-1(Dx).

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

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

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

Розглянемо функцію f(x, y)= Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ t(x) така, що для всіх х, yNf(x, y)=t(x)(у). Зафіксуємо х. Mаємо уDt(x)  t(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, vN маємо 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) така, що для всіх х, yN маємо Ds(x,y)=DxDy .

Розглянемо функцію f(x, y, z)= Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s(x, y) така, що для всіх х, y, zN маємо f(x, y, z)=s(x,y)(z). Зафіксуємо х та y. Маємо zDs(x,y)  s(x,y)(z)  f(x, y, z)  zDxDy . Звідси випливає Ds(x,y)=DxDy .

Loading...

 
 

Цікаве