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

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

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

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

слово , 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, z N маємо s(x,y)(z)= x(z)+ y(z).
Розглянемо функцію f(x, y, z)= x(z)+ y(z). Функція f є ЧРФ, тому за s-m-n-теоремою існує РФ s(x, y) така, що для всіх х, y, z N маємо 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) така, що для всіх х, y N маємо g(x, y)= s(x)(у). Зафіксуємо х. Mаємо у Ds(x) s(x)(у) g(x, y) x(f(y)) f(y) Dx 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)= 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) така, що для всіх х, y N f(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, 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)= s(x,y)(z). Зафіксуємо х та y. Маємо z Ds(x,y) 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)= s(x,y)(z). Зафіксуємо х та y. За побудовою функції f маємо Ds(x,y)=Еs(x,y). Тепер z Еs(x,y) z Ds(x,y) s(x,y)(z) f(x, y, z) z Dx Dy . Звідси отримуємо Ds(x,y)=Еs(x,y)=Dx Dy .
4. ТЕОРЕМИ КЛІНІ ПРО НЕРУХОМУ ТОЧКУ
Теорема 4.1. Нехай f (n+1)-арна РФ. Тодi iснує n-арна РФ g така, що = для всiх значень x1, ..., xп.
Переформулюємо теорему 7.4.1 для випадку n=0.
Теорема 4.2. Нехай f(x) РФ. Тодi iснує n N таке, що n = f(n).
Первісне формулювання самого С.Кліні теореми про нерухому точку має наступний вигляд:
Теорема 4.3. Нехай h(z, x) ЧРФ. Тодi iснує n N таке, що для всiх x маємо h(n, x)= n(x).
Теорему Клiнi про нерухому точку краще називати теоремою про псевдонерухому точку. Справдi, умова n= f(n) зовсім не означає, що n=f(n), a свiдчить тiльки про те, що n та f(n) iндекси однієї i тої ж ЧРФ.
Приклад 1. МНР-програму P назвемо самотворною, якщо для довiльного x N маємо P(x) (P), де (P) код програми P. На перший погляд, таких програм бути не може, бо для побудови P треба знати (P) тобто саму програму P. Проте МНР-програма P така, що P(x) (P) для всiх значень x, таки існує.
Справді, вiзьмемо функцiю h(z, x)=z. За теоремою 7.4.3 iснує таке n, що для всiх x h(n, x)= n(x). Отже, n(x)=h(n, x)=n для всiх x. Тому програма P з кодом n шукана.
Приклад 2. Існує n N таке, що для всiх x маємо n(x)=2n+x3n.
Вiзьмемо функцiю h(z, x)=2z+x3z. За теоремою 7.4.3 iснує таке n, що для всiх x h(n, x)= n(x). Отже, n(x)=h(n, x)=2n+x3n для всiх x.
Приклад 3. Існує n N таке, що Dn=En={n}.
Вiзьмемо функцiю h(z, x)= Така h є ЧРФ. За теоремою 7.4.3 iснує таке n, що для всiх x маємо h(n, x)= n(x). Тоді n(x)= Звідси Dп=Еп={n}.
Приклад 5. Існує n N таке, що Dп=En=N{n, 2n}.
Вiзьмемо функцiю h(z, x)= Така h є ЧРФ. За теоремою 7.4.3 iснує таке n, що h(n, x)= n(x) для всiх x. Тоді n(x)= Звідси Dп=En=N{n, 2n}.
Приклад 4. Існує n N таке, що Dп=Еп={x | x непарнe} {2, 4, ..., 2п}.
Функцiя h(z, x) = є ЧРФ за ТЧ. За теоремою 7.4.3 iснує таке n, що h(n, x)= n(x) для всiх x. Тоді n(x) = Звідси маємо Dп=En={x | x непарнe} {2, 4, ..., 2п}.
Приклад 6. Існує n N таке, що Dп=Еп={x | n(3x) } {x | x парнe}.
Функцiя h(z, x) = є ЧРФ за ТЧ. За теоремою 7.4.3 iснує таке n, що h(n, x)= n(x) для всiх x. Тоді маємо n(x) = Звідси отримуємо Dп=Еп={x | n(3x) } {x | x парнe}.
Приклад 7. Існує РФ g(x) така: Dg(x)=Еg(x)={3g(x)+2x} для всіх х N.
Функція h(t, x, y)= є ЧРФ за ТЧ. За s-m-n-теоремою існує РФ s(t, x) така: h(t, x, y)= s(t,x)(y) для всіх t, x, y N. За теоремою 7.4.1 існує РФ g така, що g(x)= s(g(x),x) для всіх x N. Тоді g(x)(у)= s(g(x),x)(у)=h(g(x), x, y)= Звідси для кожного x N маємо Dg(x)=Еg(x)={3g(x)+2x}.
Теорема 4.4. Для кожної РФ f(x) iснує строго монотонна РФ (x) така, що для кожного n N маємо (n) = f( (n)).
Наслiдок. Для кожної РФ f(x) та для кожного k N iснує n N таке, що n>k та n= f(n).
Розглянутi нами ефективнi нумерацiї ЧРФ неоднозначнi. Одно-значнi ефективні нумерацiї ЧРФ iснують [6], але немає в певному смислi "природних" однозначних ефективних нумерацiй ЧРФ.
Теорема 4.5. Нехай f(x) строго монотонна тотальна функцiя така, що з умови m n випливає f(т) f(n) , причому f(n) є найменшим iндексом функцiї f(n) . Тодi функцiя f не є ЧРФ.
Loading...

 
 

Цікаве