Зміст
Введення
1. Теорема про нерухому крапку
2.1 Нерухома точка і відносини еквівалентності
2.2 Системний трюк: ще одне доказ
2.3 Кілька зауважень
3. Практична частина
Висновок
Список літератури
Введення
Рекурсивні функції (від позднелатинского recursio - повернення), назва, що закріпилася за одним з найбільш поширених варіантів уточнення загального поняття арифметичного алгоритму, тобто такого алгоритму, допустимі вихідні дані якого являють собою системи натуральних чисел, а можливі результати застосування є натуральними числами. Рекурсивні функції були введені в 30-х рр.. 20 в. С.К. Кліні, в свою чергу грунтується на дослідженнях К. Геделя, Ж. Ербрана та ін математиків.
Теорема (Кліні) про нерухомої точці є основним інструментом дослідження в теорії рекурсивних функцій. Це глибокий результат в тому сенсі, що він дає витончений і економічний метод поводження з конструкціями, що в іншому випадку вимагало б довгих і складних міркувань.
Ця теорема може бути приведена в декількох формах і може розглядатися з кількох точок зору. У певному сенсі теорема підсумовує певний клас діагональних методів, включаючи метод, використовуваний для побудови рекурсивно-перечислимого, але не рекурсивного множин. З іншого боку, ця теорема встановлює деякий результат про нерухому крапку і, подібно теоремам про нерухому крапку з математичного аналізу, може бути використана для доказу існування багатьох неявно заданих функцій.
1. ТЕОРЕМА Про Нерухомої точки
1.1 Нерухома точка і відношення еквівалентності
Теорема 1. Нехай U - головна обчислювана універсальна функція для класу вичіслімих функцій одного аргументу, ah - довільна всюди певна обчислювана функція одного аргументу. Тоді існує таке число n, що Un = Uh (n), тобто n і h (n) - номери однієї функції.
Іншими словами, не можна знайти алгоритму, перетворюючого програми, який би по кожній програмі давав іншу (не еквівалентну їй). Цю теорему називають теоремою Кліні про нерухому точці або теоремою про рекурсії.
Розглянемо довільне відношення еквівалентності (яке ми будемо позначати x у) на множині натуральних чисел. Ми покажемо, що наступні дві властивості цього відношення не можуть виконуватися одночасно:
Для всякої обчислюваною функції f існує всюди певна обчислювана функція g, що є її-продовженням (Це означає, що якщо f (x) визначено при деякому x, то g (х) f (x)).
Існує всюди певна обчислювана функція h, не має-нерухомої точки.
Якщо x в - відношення рівності (x = у), то друга властивість виконано (покладемо, наприклад, h (n) = n + 1), тому не виконано перше. Теорема про нерухому точку вийде, якщо x = У розуміти як Ux = Uy (x і y - номери однієї і тієї ж функції). У цьому випадку виконано перше властивість, як ми зараз переконаємося, і тому не виконано друге.
Чому виконано перше властивість? Нехай f - довільна обчислювана функція одного аргументу. Розглянемо функцію V (n, x) = U (f (n), x). Оскільки U є головною універсальною функцією, знайдеться всюди певна функція s, для якої V (n, x) = U (s (n), x) при всіх n і х. Ця функція і буде шуканим-продовженням. У самому справі, якщо f (n) визначено, то s (n) буде іншим номером тієї ж функції, що і f (n). (Відзначимо, що якщо f (n) не визначено, то s (n) буде одним з номерів ніде не певної функції.)
Для завершення доведення теореми про нерухому крапку залишилося перевірити, що зазначені дві властивості відношення еквівалентності несумісні. Візьмемо обчислювана функція f, від якої ніяка обчислювана функція не може відрізнятися всюди (наприклад, діагональну функцію х в†’ U (x, х) для деякої обчислюваною універсальної функції U). За припущенням існує всюди певний вичіслімості-продовження g функції f. Розглянемо функцію t (x) = h (g (x)), де h - обчислювана всюди визначена функція, яка не має-нерухомою точки. Тоді t буде всюди відрізнятися від f. У самому справі, якщо f (x) визначено, то f (x) g (х) h (g (x)) = t (x), і тому f (x) t (x). Якщо ж f (x) не визначено, то цей факт сам по собі вже відрізняє f (x) і t (x).
Теорему про нерухомої точці можна переформулювати і так:
Теорема 2. Нехай U (n, x) - головна обчислювана універсальна функція для класу вичіслімих функцій одного аргументу. Нехай V (n, x) - довільна обчислювана функція. Тоді функції U і V збігаються на деякому перетині: знайдеться таке р, що Up = Vp, тобто U (p, n) = V (p, n) для будь-якого n.
Так як функція U є головною, знайдемо таку всюди певну обчислювана функція h, що V (n, x) = U (h (n), x) при всіх n і x. Залишилося взяти в якості р нерухому точку функції h.
(Приклад слідства з цієї теореми: як би не старалися розробники, для будь-яких двох версій компілятора існує програма, яка однаково працює в обох версіях - наприклад, зациклюється і там, і там. Втім, це все ж не напевно, а тільки якщо компілятор задає головну універсальну функцію - але треба дуже постаратися, щоб це було не так!)
Повчально розгорнути ланцюжок наведених міркувань і простежити, як будується нерухома точка. Для наочності замість U (n, x) ми будемо писати [n] (x) і читати це В«Результат застосування програми n до входу x В»;
Міркування починається з розгляду В«діагональноїВ» функції U (x, x), яку тепер можна записати як [x] (x) (результат застосування програми x до себе). Далі ми будуємо її всюди певне-продовження. Це робиться так. Вираз [[x] (x)] (у) вичіслімості залежить від двох аргументів. Ми згадуємо, що U є головна універсальна функція, і знаходимо таку програму g, що [[g] (x)] (y) = [[X] (x)] (у) при всіх x і у. При цьому [g] (x) визначено для всіх x. Нехай ми хочемо знайти нерухому точку програми h. Ми розглядаємо композицію [h] ([g] (x)). Це вираз вичіслімості залежить від x, і тому існує програма t, для якої [t] (x) = [h] (g (x)) при всіх x. Ця програма застосовна до всіх x, оскільки такі h і g. Тепер нерухомою точкою буде [g] (t). Щоб переконатися в цьому, ми повинні перевірити, що [[g] (t)] (x) = [h ([g] (t))] (x) для всіх x. У самому справі, по властивості g маємо [[g] (t)] (x) = [[t] (t)] (x). Згадуючи визначення t, цей вираз можна переписати як [[H] ([g] (t))] (x) - що якраз і було потрібно.
1.2 Системний трюк: ще один доказ
Якщо попросити любителів різних мов програмування написати на своєму улюбленому мовою по можливості коротку програму, яка б друкувала свій вихідний текст, то чемпіоном, швидше за все, виявиться коротка програма на Бейсіку:
10 LIST
Справа в тому, що в Бейсіку є команда LIST, яка друкує текст програми і може бути запущена зсередини програми.
Перш за все, це гарна жарт. Але можна поставитися до неї несподівано серйозно і використовувати цю ідею в ще одному доведенні теореми про нерухому крапку (точніше, в ще одному варіанті того ж докази).
Насамперед зазначимо, що теорему досить довести для якоїсь однієї головної нумерації. У самому справі, нехай для якоїсь іншої головної нумерації існує функція без нерухомою точки, тобто мається спосіб перетворювати програми у свідомо нееквівалентні. Тоді за допомогою трансляції туди і назад такий спосіб
можна знайти і для першої нумерації (для якої ми теорему вважаємо доведеною).
Тепер розглянемо мову програмування, в якому крім звичайних можливостей є вбудована процедура
GetProgramText (var s: string)
Ця процедура поміщає текст вихідної програми в рядок s. Незважаючи на деяку незвичайність цієї ідеї, цілком можна уявити собі інтерпретатор цієї мови - і інтерпретація цієї процедури не представляє праці, так як інтерпретатору, зрозуміло, доступний текст програми. Зробимо ще один крок і уявімо собі, що в цьому мові є також процедура
ExecuteProgram (s: string)
Ця п...
