На головну

 Інтуїтивне поняття алгоритму |  властивості алгоритмів |  Уточнення поняття алгоритму |  Вправа |  вправи |  Вправа |  Нумерація програм для МНР |  Нумерація обчислюваних функцій |  Вправа |  універсальні програми |

S-m-n-теорема

У цьому розділі ми доведемо теорему, що належить до числа основних результатів теорії алгоритмів. Суть теореми в наступному. Припустимо, що f(х, у) - Обчислювана функція. Для кожного фіксованого значення a змінної х функція f породжує одномісну обчислюваної функції ga(y) = f(a, у). З обчислюваності функції ga слід існування індексу b такого, що f(a, у) = fb(у). виявляється індекс b можна ефективно обчислити по параметру а.

Теорема 8.1 (s-m-n-теорема, Проста форма). нехай f(х, у) -вичіслімая Функція. Існує всюди певна обчислювана функція s(x), Така, що f(х, у) = fs (x)(у).

Доведення. З обчислюваності функції f(х, у) Слід існування МНР-програми Pr, Яка, виходячи з початкової конфігурації (x, y, 0, 0, ...), Обчислює значення функції f від двох аргументів х и у. змінимо програму Pr, Додавши попереду команди, що перетворюють початкову конфігурацію

R1 R2 R3 R4 ...  
y 0 0 0 ...  (*)

в конфігурацію

R1 R2 R3 R4 ...
a y 0 0 ...

наступним чином:

T(1, 2)

Z(1)

Pr

Нова програма Pr1, Застосована до початкової конфігурації (*), обчислює значення функції ga(y) = f(a, у) Від одного аргументу у.

Тепер розглянемо функцію s(a) = G (Pr1), Що зіставляє довільному неотрицательна цілому числу a Геделем номер програми Pr1. функція s всюди визначена і по тези Черча обчислюваності. Крім того, з побудови fs (a)(у) = f(a, у) для кожного .

Зауваження 8.1. Сформульовану теорему називають також теоремою параметризації, Оскільки вона дозволяє за заданою обчислюваної функції f(x, у) І фіксованому параметру a знайти Геделем номер s(a) Програми, що обчислює функцію fs (a)(у) = f(a, у).

Доведена вище теорема 8.1 є окремим випадком більш загальної теореми.

Теорема 8.2 (s-m-n-теорема). нехай m, n - натуральні числа,  - Обчислювана функція з геделевим номером a. Існує всюди певна обчислювана функція  така, що

.

Доказ сформульованого твердження аналогічно доведенню теореми 8.1.

Зауваження 8.2. Назва теореми 8.2 пов'язано з позначенням  для функцій в формулюванні теореми.

Покажемо тепер, як можна використовувати s-m-n-теорію для доказу нерозв'язності проблем. s-m-n-теорема часто використовується для зведення проблеми «  »До інших проблем.

Теорема 8.3. проблема «  »нерозв'язна.

Доведення. Розглянемо функцію

За тези Черча функція f(x, y) Обчислюваних. Звідси по s-m-n-теоремою випливає існування всюди певної обчислюваної функції s (x) такий, що  . За визначенням функції f(x, y) Маємо:

.

Отже, істинність умови  можна встановити, визначивши справедливість рівності  . Тим самим ми звели проблему «  »До проблеми«  ». Оскільки перша з них нерозв'язна, то нерозв'язна і друга.

Зауваження 8.3. Теорема 8.3 показує, що в області перевірки правильності комп'ютерних програм є принципові обмеження. У ній йдеться про те, що не існує алгоритму перевірки того, чи буде програма обчислювати нульову функцію. Кілька змінивши доказ теореми 8.3, можна переконатися в тому, що те ж саме справедливо і для будь-якої іншої конкретної обчислюваної функції.

Теорема 8.4. проблема  нерозв'язна.

Доведення. Припустимо, що проблема  вирішувана. Тоді можна вирішити і проблему  , де c - Індекс функції 0  . Однак, це суперечить теоремі 8.3. Таким чином, проблема  нерозв'язна.

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



 Алгоритмічно нерозв'язні проблеми |  вправи
© um.co.ua - учбові матеріали та реферати