2. Теорія рекурсивних функцій та її застосування для встановлення нерозв`язності масових проблем icon

2. Теорія рекурсивних функцій та її застосування для встановлення нерозв`язності масових проблем



Схожі
Тема 2. Теорія рекурсивних функцій та її застосування для встановлення

нерозв`язності масових проблем.

В даній темі ми розглянемо теорію рекурсивних функцій та схему її застосування для встановлення нерозв`язності 10-ї проблеми Гільберта.

Лекція 50. Рекурсивні функції


1. Примітивно-рекурсивні, частково-рекурсивні та загально-рекурсивні функції.

Далі ми будемо оперувати лише зі словами в деякому алфавіті. Для представлення раціональних чисел окрім символу “I” вводиться також символ “/”. Тоді – представлення числа .

Будемо розглядати функції на множині натуральних чисел, включаючи нуль: N{0}. Серед функцій, заданих на цій множині будемо виділяти скрізь визначені функції (: N  N), коли для кожного елементу множини N визначена відповідність із N, і частково визначені функції. Можливе розглядання n-місних функцій : N ... N  N.

Із усіх цих функцій виділимо три функції:

1. Нуль-функція: O(х) = 0, для x.

2. Наступний елемент: S(x) = x+1.

3. Індексна функція: (x1, ... , xn) = xm.

Ці три функції входять в означення будь-якої рекурсивної функції. Рекурсивні функції вводяться задаванням спеціальних операторів над функціями. Застосовуючи скінчене число операторів до наших трьох функцій, будемо отримувати рекурсивні функції. В залежності від того, які оператори ми можемо застосовувати, в класі рекурсивних функцій виділяються:

  • примітивно-рекурсивні функції;

  • частково- рекурсивні функції;

  • загально- рекурсивні функції.


2. Означення операторів над функціями.

Означення 1. Будемо говорити, що m-місна функція (x1, ... , xm) отримана суперпозицією із n-місної функції g та m-місних функцій , , ... , , якщо (x1, ... , xm) = g((x1, ... , xm), (x1, ... , xm), ... , (x1, ... , xm)).

Означення 2. Будемо говорити, що (n +1)-місну функцію  можна отримати з допомогою примітивної рекурсії із n-місної функції g та (n +2)-місної функції h, якщо:

(x1, ... , xn, 0) = g(x1, ... , xn),

(x1, ... , xm, y+1) = h (x1, ... , xn, y, (x1, ... , xn, y)).

Означення 3. Нехай задана деяка функція (x1, ... , xn). Зафіксуємо значення x1, ... , xn і розглянемо рівняння (x1, ... , xn-1, y) = xn. Якщо функція визначена для значень (x1, ... , xn-1, 0), (x1, ... , xn-1, 1), ... , то ми можемо знайти найменше значення y, при якому виконується рівняння. Це найменше значення y позначимо My((x1, ... , xn-1, y) = xn). Якщо функція  задана, то через n її аргументів визначається нова функція Mf, яка отримана за допомогою оператора мінімізації М.

Функція Mf може бути не скрізь визначеною, тому вводиться оператор слабкої мінімізації.

Означення 4. Нехай задана функція . Тоді бедемо говорити, що функція визначена за допомогою оператора слабкої мінімізації над , тобто, якщо = Mf, коли  всюди визначена, і невизначена в протилежному випадку.


3. Означення класів рекурсивності.

Означення. Будемо називати функцію примітивно-рекурсивною, якщо вона отримана за допомогою скінченого числа застосувань операторів суперпозиції і примітивної рекурсії до початкових трьох функцій (нуль-функції, наступного елемента та індексної функції).

Означення. Будемо говорити, що функція примітивно-рекурсивна відносно системи функцій , якщо вона отримана скінченим числом застосувань операторів суперпозиції та примітивної рекурсії до функцій із , і до початкових трьох функцій.

Очевидно, що усі початкові функції є всюди визначеними. В такому випадку, із означення оператора суперпозиції ми можемо стверджувати, що суперпозиція скрізь визначених функцій є всюди визначеною функцією.

Якщо функція  визначена через примітивну рекурсію над функціями g і h, то ми можемо для будь-якого набору значень аргументів x1, ... , xn, y “вирахувати” цю функцію таким чином: (x1, ... , xn, 0) = g(x1, ... , xn). Якщо g всюди визначена, то і (x1, ... , xn, 0) буде всюди визначена. Визначимо (x1, ... , xn, 1) через h. Якщо h всюди визначена для всіх значень аргументів, то і (x1, ... , xn, 1) теж визначена. Повторюючи цей процес, ми можемо дійти до значення (x1, ... , xn, y). Таким чином, якщо g і h всюди визначені, то функція , яку ми визначаємо за допомогою оператора примітивної рекурсії над ними теж всюди визначена. Таким чином оператори суперпозиції та примітивної рекурсії, які застосовуються до всюди визначених функцій дають всюди визначені функції. Значить кожна примітивно-рекурсивна функція всюди визначена. Тоді виникає питання: "Чи визначена всюди кожна примітивно-рекурсивна функція відносно ?". А це залежить від системи функцій .

Означення. Будемо називати функцію частково-рекурсивною, якщо вона отримана скінченим числом застосувань операторів суперпозиції, примітивної рекурсії та мінімізації до початкових функцій.

Із означення випливає, що кожна примітивно-рекурсивна функція є частково-рекурсивною і якщо ми покажемо, що існує частково-рекурсивна функція, яка не всюди визначена, то тоді примітивно-рекурсивні функції є власною підмножиною частково-рекурсивних функцій.

Означення. Будемо називати функцію частково-рекурсивною відносно системи , якщо вона отримана скінченим числом застосувань операторів суперпозиції, примітивної рекурсії та мінімізації до функцій системи , та до початкових функцій.

Означення. Будемо називати функцію загально-рекурсивною, якщо вона отримана скінченим числом застосувань операторів суперпозиції, примітивної рекурсії та слабкої мінімізації над початковими функціями.

Кожна примітивно-рекурсивна функція є загально-рекурсивною. Протилежне відношення має свої особливості, які ми розглянемо далі.


4. ^ Встановлення рекурсивності деяких відомих функцій.

Усі функції визначені на множині N{0}.

Функція O(x1, ... , xn) – рекурсивна, оскільки її множину можна визначити як індексну, а потім до індексного значення застосувати O(x).

Константа а – рекурсивна. Використовуємо суперпозицію. Починаємо із початкової функції O(x). Потім використовуємо скінчене число операцій суперпозиції S(S ... (O(x))...).

Функція f(x,y) = x + y – примітивно-рекурсивна. Використовуємо оператор примітивні рекурсії:

а) x + 0 обчислюємо як індексну функцію (x) = x;

б) x+(y+1) = (x+y)+1, тобто може бути обчислене як функція наступного елементу від результату, отриманого на попередньому кроці.

Отже маємо схему примітивної рекурсії для функції f(x,y):

.

Коли ми будуємо схеми рекурсії, то функції , для яких ми довели рекурсивність, можна використовувати як “цеглинки” при доведенні рекурсивності інших функцій.

Функція f(x,y)=xy – примітивно-рекурсивна. Також використовуємо оператор примітивної рекурсії:

а) x0 = 0 - на першому кроці – це нуль-функція.

б) x(y + 1) = xy + x – примітивна рекурсія.

Замість h використовується функція від аргументу x та від значення функції на попередньому кроці: (x, y) + x – додавання.

– примітивна рекурсія

отримали за схемою примітивної рекурсії, де g = const, h = f(x,y)*x

та – обидві рекурсивні

На множині натуральних чисел функція f(x,y)=x-y є частковою.

Дійсно:

– часткова функція

Тому введемо спочатку всюди визначену функцію:

і
продемонструємо, що вона є примітивно-рекурсивною. Для цього спочатку покажемо, що x∸1 є примітивно-рекурсивною використовуючи схему примітивної рекурсії:

0∸1=0 – нуль-функція;

(x+1) ∸1=x – індексна функція.

Тепер легко встановити, за тією ж схемою, примітивну рекурсивність x∸y:

x∸0 = x

x∸(y+1) = (x∸y) ∸1.

Використовуючи оператор мінімізації:

Z = z(y+Z) = x 5-3=2

3 5

3+0=35

3+2=5 – частково-рекурсивна функція.


Висновки:

1. Таким чином ми ввели основні класи рекурсивних функцій.

2. Привели приклади функцій різноманітних класів.

Залишилося визначити обчислюваність через рекурсивність і показати нерозв`язність масових проблем за допомогою рекурсивності.

^ Лекція 51. Обчислюваність, розв`язність та рекурсивність.

Оскільки рекурсивність – це поняття, яке виникає в зв’язку з необхідністю уточнення алгоритму, то нам необхідно визначити в термінах рекурсивних функцій поняття обчислюваності (алгоритмічної) та розв`язності.


1. ^ Рекурсивна обчислюваність.

Оскільки при визначенні рекурсивної функції, ми одночасно показували прості механізми отримання їх значень для довільних аргументів, починаючи із найменших, то очевидно, що через рекурсивність можна визначити обчислюваність.

Існує добре обгрунтована, що не підлягає доведенню, теза Черча по відношенню до рекурсивних функцій:

клас обчислюваних функцій співпадає з класом частково-рекурсивних функцій.

Довести цю тезу неможливо через те, що рекурсивність – це уточнення інтуїтивного поняття, а обгрунтовано воно тим, що всі існуючі алгоритми визначені як схеми обчислення деяких рекурсивних функцій. Тезу можна тільки заперечити, якщо знайдеться алгоритм, для якого не можна буде знайти рекурсивну схему.

Як практичний результат можна відзначити встановлення обчислюваності довільної функції (х) за допомогою її побудови як рекурсивної функції.

Класи частково-рекурсивних функцій і функцій, що є обчислюваними за Тьюрінгом співпадають. Оскільки ми вже маємо два способи уточнення обчислюваності: за Тьюрінгом та рекурсією, то можна проаналізувати ці два способи на предмет еквівалентності. Доведено, що все те, що можна виразити у вигляді вираховного за Тьюрінгом, можна обчислити за допомогою рекурсії і навпаки. Рекурсивні функції – це апарат, який найчастіше використовується для встановлення обчислюваності і розв`язності. Все розглядається на прикладах примітивної рекурсії. Існують рекурсії 2-го порядку і т.д. (за двома аргументами і більше).


2. ^ Рекурсивна розв`язність.

Згадаємо, що множина M1 розв’язувана відносно M, якщо існує алгоритм, який для будь-якого елемента множини M дає відповідь за скінчену кількість кроків: належить він M1 чи ні. З точки зору рекурсивних функцій далі під множиною M будемо розуміти множину всіх натуральних чисел N{0}, а N1 буде її довільною підмножиною: N1  N.

Залишається пов’язати розв`язність з одним із класів рекурсивних функцій. Звичайно, краще це зробити для частково-рекурсивних функцій. Для цього вводиться поняття характеристичної функції. (х) – характеристична функція множини N1, якщо:



Але, якщо множина N1 розв`язувана відносно N, це означає, що ми можемо обчислити значення характеристичної функції даної множини. Дійсно, якщо елемент хN1, то (х) = 0. Якщо ж алгоритм розв`язності встановить, що xN1, то (х) = 1.

З іншого боку, обчислюваними функціями, як ми вже визначили є частково-рекурсивні. Таким чином, множина N1 розв`язувана відносно N, якщо його характеризує частково-рекурсивна функція.

Аналогічно введемо поняття примітивно-рекурсивної множини.

Означення. Множину N1 будемо називати примітивно-рекурсивною, якщо її характеристична функція примітивно-рекурсивна.

Означення. Функція (х) називається частковою характеристичною функцією множини N1, якщо:



Означення. Якщо часткова характеристична функція множини N1 є частково-рекурсивною, то множину назвемо частково-рекурсивною.

Рекурсивні множини – це найбільш важливі множини, оскільки це ті множини, для яких розв`язна проблема входження елементів, тобто це рзв`язувані множини.


Розглянемо проблему: нехай задана система двох рівнянь з двома невідомими, коефіцієнти – натуральні числа.



Якщо ми конкретизуємо значення коефіцієнтів а1, b1, с1, а2, b2, с2, то ми отримаємо конкретизацію даної масової проблеми, яка або буде мати розв’язок, або ні. Тоді виникає проблема розв`язності конкретизацій, які мають розв’язок, відносно всіх конкретизацій.

Якщо М – множина всіх шісток із натуральних чисел <а1, b1, с1, а2, b2, с2>, а під M1 маємо ті шістки, для яких відповідна конкретизація має розв’язок.

Нам необхідно встановити розв`язність М1 відносно М, тобто показати, що характеристична функція множини М1 частково-рекурсивна. Оскільки означення зроблені відносно множини N1 натуральних чисел, то необхідно їх узагальнити на розглядувані конструкції із n-ок (як наші шістки) і взагалі на будь-які символьні конструкції, в частковому випадку терми. Для цього використовується кодування та нумерацію.

Нумерація n-ок – це процес надавання кожній n-ці такого натурального числа, що кожна n-ка отримає якесь одне число, і лише одне число відповідає кожній n-ці.

Означення: Множина N1 – рекурсивна, якщо її характеристична функція – частково-рекурсивна.

Для 2-ок номера отримуються позицією в послідовності:

<0, 1>, <1, 0>,

<0, 2>, <1, 1>, <2, 0>,

<0, 3>, <1, 2>, <2, 1>, <3, 0>, і т.д.,

тобто двійки впорядковуються за сумою двох чисел, а якщо декілька двійок мають одну суму, то впорядковуються за збільшенням першого елемента. Тоді номером, про який іде мова для пари <х, у> буде:

.

На випадок трійок використовуємо перетворення: C(х1, х2, х3) = C(C(х1, х2), х3).


3. Деякі властивості рекурсивних та примітивно-рекурсивних множин. Рекурсивно-перераховні множини.

Рекурсивні та примітивно-рекурсивні множини мають цікаві особливості.

Теорема 5.7. Доповнення рекурсивної (примітивно-рекурсивної) множини рекурсивне (примітивно-рекурсивне). Об’єднання та перетин скінченої кількості рекурсивних (примітивно-рекурсивних) множин є множина рекурсивна (примітивно-рекурсивна).

Доведення.

Схема доведення стандартна для теорії рекурсивних функцій. Покажемо загальну схему доведення для подібних властивостей:

а) побудова характеристичної функції результату;

б) встановлення її часткової рекурсивності (примітивної рекурсивності).

1. Доповнення до N1.

Нехай характеристична функція множини N1: (x). Тоді характеристична функція доповнення до N1: (x) =((x)). Якщо (x) – примітивно-рекурсивна (частково-рекурсивна), то функція sg теж примітивно-рекурсивна (частково-рекурсивна).

2. Об’єднання множин: N1...Nk.

Характеристична функція: (x) = (x)...(x). Якщо – примітивно-рекурсивні (частково-рекурсивні), то функція примітивно-рекурсивна (частково-рекурсивна).

3. Перетин множин: N1...Nk.

Характеристична функція: (x) = sg((x) + ... + (x)). Використаємо ті ж міркування.

^ Теорема доведена.

Одне із важливих властивостей примітивної рекурсії пов’язане з тим, що рівняння на основі примітивно-рекурсивних функцій мають примітивно-рекурсивні множини розв’язків. Це ж характерно і для всюди визначених частково-рекурсивних функцій.

Справедлива наступна

Теорема 5.8. Якщо (x) примітивно-рекурсивна (всюди визначена частково-рекурсивна) функція, то множина розв’язків рівняння (x) = 0 примітивно-рекурсивна (рекурсивна).

Доведення.

g(x) – характеристична функція множини розв’язків: g(x) = sg((x)).

Якщо (x) – примітивно-рекурсивна, то множина розв’язків примітивно-рекурсивна. Якщо (x) – всюди визначена частково-рекурсивна функція, то множина розв’язків рекурсивна.

^ Теорема доведена.

Оскільки апарат рекурсивних функцій використовується для понять уточнення обчислюваності і розв`язності і виник у зв’язку з необхідністю встановлення нерозв`язності ряду масових проблем, то аналогічно уточненню поняття розв`язності, необхідно уточнення поняття нерозв`язності.

В принципі, разом із примітивно-рекурсивними та рекурсивними множинами, з якими асоціюється поняття розв`язності, в теорії рекурсивних функцій використовується поняття рекурсивно-зліченних, продуктивних та креативних множин, які асоціюються з поняттям нерозв`язності.

Ми розглянемо тільки рекурсивно-зліченні множини, безпосередньо пов’язані з встановленням нерозв`язності 10-ї проблеми Гільберта (хоча в доведенні допоміжних положень використовуються й інші класи множин).


4. ^ Деякі властивості рекурсивно-зліченних функці.

Означення. Множину натуральних чисел N1 будемо називати рекурсивно-зліченною, якщо існує двомісна примітивно-рекурсивна функція (n, x) така, що рівняння (n, x) = 0 має розв’язок х тоді і тільки тоді, коли nN1.

По відношенню до рекурсивно-зліченних множин виконуються деякі властивості, аналогічні властивостям примітивно-рекурсивних та рекурсивних множин.

Справедлива наступна

Теорема 5.9. Об’єднання та перетин скінченої кількості рекурсивно-зліченних множин є рекурсивно-зліченною множиною.

Доведення.

Нехай N1, ... , Nm - рекурсивно-зліченні множини; (n, x1), ... ,(n, xm) - відповідні їм примітивно-рекурсивні функції.

Для N=N1...Nm будуємо примітивно-рекурсивну функцію: =(n, x1)...(n, xm). Тоді рівняння = 0 має розв’язок тоді і тільки тоді, коли nN.

Для N=N1...Nm примітивно-рекурсивна функція: =(n, x1) +...+(n, xm).

Теорема доведена.

Але в той же час властивості доповнення для рекурсивно-зліченних множин мають свої особливості. Справедлива наступна

Теорема 5.10. (Поста) Нехай множина натуральних чисел N1 рекурсивно-зліченна, а множина 1 – її доповнення. Доповнення рекурсивно-зліченної множини рекурсивно-зліченне тоді і тільки тоді, коли вони обидві рекурсивні.

Доведення.

а) Пряма теорема.

Нехай множини N1 і 1 рекурсивно-зліченні. Покажемо їх рекурсивність. Якщо вони рекурсивно-зліченні, то вони мають примітивно-рекурсивні функції. Нехай N1 має примітивно-рекурсивну функцію (n, x), а 1 – g(n, x). Ми розглядали нумерацію пар <х, у> з номерами С(х, у). Існує і протилежна відповідність: якщо t - це номер пари, t = С(х, у), то l(t) = х і r(t) = у. Кожна із функцій l ³ r примітивно-рекурсивна. Очевидно, (n, x)g(n, x) = 0 має розв’язок для nN.

Далі h(n) = x((n, x)g(n, x)) = 0 примітивно-рекурсивна і всюди визначена, тобто загальнорекурсивна функція. sg(h(n)) – всюди визначена і є характеристичною функцією для множини N1, тоді N1 рекурсивна і 1 рекурсивна (за вище наведеною теоремою).

б) Обернена теорема.

Обернена теорема лишається під запитанням. Якщо є дві рекурсивні множини, вони рекурсивно-зліченні чи ні?

^ Теорема доведена.

Одним із найважливіших результатів відносно рекурсивно-зліченних множин є той факт, що рекурсивно-зліченні множини співпадають із множинами значень примітивно-рекурсивних функцій. Вже було доведено, що в визначенні рекурсивно-перелічувальних множин може використовуватись будь-яка частково-рекурсивна функція.

Справедлива наступна

Теорема 5.11. Множина натуральних чисел N1 рекурсивно-зліченна тоді і тільки тоді, коли вона співпадає з множиною значень деякої примітивно-рекурсивної функції.

Доведення.

а) Пряма теорема.

Нехай N1 – множина значень деякої примітивно-рекурсивної функції (x). Покажемо, що N1 рекурсивно-зліченна множина.

Для N1 відповідною примітивно-рекурсивною функцію буде функція (x)  n (вона примітивно-рекурсивна за побудовою). Дійсно, рівняння (x)  n= 0 має розв’язок тоді і тільки тоді, коли nN1. Значить N1 рекурсивно-зліченна множина.

б) Обернена теорема.

Нехай N1 рекурсивно-зліченна множина. Покажемо, що існує така примітивно-рекурсивна функція, що множина її значень співпадає з N1.

Побудуємо примітивно-рекурсивну функцію:

h(t) = l(t) ((l(t), r(t))) + bsg((l(t), r(t))),

де l(t), r(t) – це ліва та права частини пари (х, у) відповідно, яка за функцією С(х, у) набуває значення t.

Множина значень h(t) співпадає з N1 (b – довільний елемент множини N1). Дійсно, якщо nN1, то (n, x) = 0 має розв’язок, а звідси випливає

((l(t), r(t))) = 1, h(t) = n.

Якщо nN1, то (n, x) = 0 розв’язку не має, ((l(t), r(t))) = 0 і h(t) = b (bN1).

^ Теорема доведена.

Ця теорема має велике значення і досить часто її результат використовується як друге означення рекурсивно-перераховних множин:

Означення. Множина буде рекурсивно-перераховною, якщо вона співпадає із множиною значень примітивно-рекурсивної функції.

При цьому треба відмітити, що існують також примітивно-рекурсивні функції, множини яких є рекурсивними.

Справедлива наступна

Теорема 5.12. Множина значень примітивно-рекурсивної (всюди визначеної частково-рекурсивної) функції (x), такої, що (x)  х, в частковому випадку монотонно зростаючої, є примітивно-рекурсивною(рекурсивною).

Доведення.

g(x)=sg(y)  x- характеристична функція множини значень (x).

В принципі, якщо рекурсивність пов’язана із розв`язністю і це інтуїтивно зрозуміло, то також інтуїтивно зрозуміло, що нерозв`язність пов’язана з рекурсивною перераховністю. Інтуїтивно, тепер представляється співвідношення цих понять на прикладі примітивно-рекурсивної функції (x).

Х – множина розв’язків рівняння (x). Ця множина рекурсивна і розв’язна.

Y – це множина значень: (0), (1), ... , (). Ця множина нерозв’язна.

^ Теорема доведена.

Таким чином з точки зору встановлення нерозв`язності проблем необхідно встановити відповідність (відношення) між множинами: рекурсивними і рекурсивно-перераховними.

Справедлива наступна

Теорема 5.13. Кожна примітивно-рекурсивна множина є рекурсивно-перераховною множиною.

Доведення.

Нехай N1 - примітивно-рекурсивна множина, тоді її характеристична функція (x) – примітивно-рекурсивна. Тоді функція (n) + x – двомісна примітивно-рекурсивна функція. Розглянемо рівняння (n) + x = 0. Якщо (n) = 0, тобто nN1, то очевидно, що рівняння має розв’язок x = 0. Якщо ж (n) = 1, тобто nN1, то яким би не був x, рівняння не має розв’язків (в правій частині ніколи не отримаємо нуль). Звідси випливає, що рівняння розв’язується для точок, які належать множині N1. Таким чином N1 – рекурсивно-перераховна множина.

^ Теорема доведена.

Нами доведено, що існує загально-рекурсивна функція, яка не є примітивно-рекурсивною, і на цій підставі показано, що існує примітивно-зліченна множина, яка не є рекурсивною.

^ Лекція 52. Десята проблема Гільберта. Схема встановлення нерозв`язності.

1. Десята проблема Гільберта з точки зору розв`язності на множинах.

Я
кщо ми розглядаємо рівняння F(x1, ... , xn) = 0, де F(x1, ... , xn) – многочлен із натуральними степенями та цілими коефіцієнтами, то десята проблема Гільберта містить в собі (сучасну термінологію з використанням поняття алгоритму): встановлення алгоритму, який за скінчену кількість кроків, для кожного елемента множини Д, може встановити: належить він множині Др, чи ні.

Іншими словами, мова йде про встановлення розв`язності множини розв`язних діофантових рівнянь, відносно множини всіх діофантових рівнянь за скінчену кількість кроків (розв`язності Др відносно Д).

У зв’язку з тим, що довго не вдавалося знайти такий алгоритм, було виказане припущення, що Др нерозв`язна відносно Д. Для того, щоб встановити нерозв`язність цієї проблеми можна використовувати апарат рекурсивних функцій. При цьому, із-за тієї причини, що ми переходимо до формул на натуральній множині чисел, а діофантові рівняння можуть мати цілі розв’язки, ми повинні обгрунтувати можливість використання рекурсивних функцій для даної проблеми.

Для того, щоб рівняння F(x1, ... , xn) = 0 мало цілі розв’язки необхідно, щоб рівняння:

F(x1, x2, ... , xn)F(x1, x2, ... , xn)F(x1, x2, ... , xn)...F(x1, x2, ... , xn) = 0

мало натуральні розв’язки.

За відомою теоремою Лагранжа будь-яке натуральне число може бути представлене в вигляді суми квадратів чотирьох цілих (натуральних) чисел (+++). Тоді очевидно, що для того, щоб рівняння F(x1, ... , xn) = 0 мало натуральний розв’язок необхідно, щоб рівняння

F(+++, ... ,+++) = 0

мало цілий (натуральний) розв’язок. Таким чином ми завжди можемо перейти від рівняння з цілим розв’язком до рівняння з натуральним розв’язком. Звідси випливає, що ми можемо використовувати теорію рекурсивних функцій.


2. ^ Властивість діофантовості предикатів, множин і функцій.

Означення. Назвемо предикат P(x1, ... , xn), де x1, ... , xnN, діофантовим, якщо існує многочлен F(x1, ... , xn, y1, ... , ym) такий, що P(x1, ... , xn) набуває істинного значення тоді і тільки тоді, коли існують такі y1, ... , ym, що F(x1, ... , xn, y1, ... , ym) = 0.

Легко показати, що кон’юнкція і диз’юнкція діофантових предикатів є діофантовою. Застосування квантора  до діофантового предикату дає діофантовий предикат.

Означення. Множина кортежів виду 1, ... , xn>, де xi набувають значення, які належать множині N, називається діофантовою, якщо діофантовий предикат P(x1, ... , xn) набуває істинного значення тільки на кортежах даної множини.

Таким чином ми можемо застосувати властивість діофантовості до рівнянь, які ми аналізуємо.

Очевидно, що для того, щоб десята проблема Гільберта була розв`язною, необхідно довести, що кожна діофантова множина є рекурсивною і кожна рекурсивна множина є діофантовою.

Щоб показати, що десята проблема Гільберта нерозв`язна, необхідно встановити співпадіння діофантовості з яким-небудь іншим класом множин, з яких не всі рекурсивні.

Саме ця схема була використана для десятої проблеми Гільберта та традиційно використовується для встановлення нерозв`язності масових проблем.

В теорії рекурсивних функцій показано, що виконуються наступні твердження:

1. Множина натуральних чисел діофантова тоді і тільки тоді, коли вона рекурсивно-зліченна.

2. Існує не рекурсивна рекурсивно-зліченна множина.

Другий факт доводиться, використовуючи твердження, що існує загальнорекурсивна функція, яка не є примітивно-рекурсивною.

Таким чином, якщо мені необхідно аналізувати деяку масову проблему, то її розв`язність встановляється за рахунок встановлення рекурсивності множини позитивних випадків відносно усіх випадків. Для встановлення нерозв`язності проблеми достатньо показати, що множина усіх позитивних випадків є рекурсивно-зліченною, але не рекурсивною.



Скачати 226.71 Kb.
Дата конвертації25.10.2013
Розмір226.71 Kb.
ТипЛекція
Додайте кнопку на своєму сайті:
uad.exdat.com


База даних захищена авторським правом ©exdat 2000-2012
При копировании материала укажите ссылку
звернутися до адміністрації
Документи