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

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

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

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

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

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

4. ТЕОРЕМИ КЛІНІ ПРО НЕРУХОМУ ТОЧКУ

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

Переформулюємо теорему 7.4.1 для випадку n=0.

Теорема 4.2.Нехайf(x)  РФ. Тодi iснуєnNтаке, що n = f(n).

Первісне формулювання самого С.Кліні теореми про нерухому точку має наступний вигляд:

Теорема 4.3.Нехай h(z, x) ЧРФ. Тодi iснує nNтаке, що для вс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льного xN маємо 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. Існує nN таке, щодля вс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. Існує nN таке, що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. Існує nN таке, що 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. Існує nN таке, що 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. Існує nN таке, що 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, yN. За теоремою 7.4.1 існує РФ g така, що g(x)=s(g(x),x) для всіх xN. Тоді g(x)(у)=s(g(x),x)(у)=h(g(x), x, y)=Звідси для кожного xN маємо Dg(x)=Еg(x)={3g(x)+2x}.

Теорема 4.4. Для кожної РФ f(x) iснує строго монотонна РФ (x) така, що для кожного nN маємо (n)=f((n)).

Наслiдок. Для кожної РФ f(x) та для кожного kN iснує nN таке, що n>k та n=f(n).

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

Теорема 4.5. Нехай f(x) строго монотонна тотальна функцiя така, що з умови mn випливає f(т) f(n) , причому f(n) є найменшим iндексом функцiї f(n) . Тодi функцiя f не є ЧРФ.

Loading...

 
 

Цікаве