Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій, Детальна інформація

4) якщо t0 та t1 \xF02D\xF020ОТ, то N\x263C(t0, t1) \xF02D ОТ.

Кожна програмована на N п-арна функція є значенням деякого ОТ ППА-Ar-N. Проте, як і у випадку ОТ алгебри п-арних ЧРФ, з-за порушень умов арності не кожен ОТ ППА-Ar-N має певне значення.

Зрозуміло, що подання програмованих на N п-арних функцій операторними термами ППА-Ar-N неоднозначне.

Нехай функції ( та ( трактуються як предикати. Тоді функції nsg((), ((( та (+( можна трактувати як предикати ((, (&( та ((( відповідно. Враховуючи, що ((( можна подати як ((((, ((( можна подати як (((()&((((), легко отримати функції, які моделюють вказані предикати.

Приклад 14. Функції-константи програмовані.

за допомогою операцій суперпозиції Sn+1.

Приклад 15. Функції пsg(x1) та sg(x1) програмовані.

.

Приклад 16. Функцiя |x1-x2| програмована.

).

Приклад 17. Предикати x1>x2, x1(x2, x1=x2 та x1(x2 програмовані.

, предикат x1=x2 можна подати у вигляді (x1(x2)&(x2(x1), предикат x1(x2 можна подати у вигляді ((x1=x2).

Приклад 18. Функція mod(x1, x2) програмована.

).

за допомогою операцій N\x263C та Sn+1.

). Отже, функцію + можна не включати до базових програмованих на N п-арних функцiй.

і операції суперпозицiї та циклу.

8. ТЕЗА ЧОРЧА

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

Теорема 8.1. Наступнi класи функцiй спiвпадають:

1) клас ЧРФ;

2) клас програмованих на N п-арних функцiй;

3) клас МНР-обчислюваних функцiй;

4) клас функцiй, обчислюваних за Тьюрiнгом;

5) клас функцiй, обчислюваних за Марковим;

6) клас функцiй, обчислюваних за Постом

Отже, розглянутi нами формалiзми задають один i той же клас п-арних функцiй на N. При цьому самi визначення формалiзмiв гарантують ефективну обчислюванiсть описуваних ними функцiй. Тому є всi пiдстави вважати, що такi формалiзми є рiзними математичними уточненнями iнтуїтивного поняття алгоритмiчно обчислюваної функцiї (АОФ). Вперше таке твердження стосовно рекурсивних функцiй було висунуте в 1936 роцi А. Чорчом, тому дiстало назву ”теза Чорча”. Узагальнення тези Чорча на випадок часткових функцiй в цьому ж роцi запропонував С. Клiнi. В такому розширеному виглядi теза Чорча формулюється наступним чином:

Tеза Чорча. Клас ЧРФ співпадає з класом п-арних АОФ, заданих на множині натуральних чисел.

Поняття АОФ не є строго визначеним математичним поняттям, тому теза Чорча математичному доведенню не пiдлягає. Теза Чорча є природно-науковим фактом, який засвідчує адекватність формальних моделей інтуїтивного поняття АОФ.

Із тези Чорча як наслiдок випливає: