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

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

ГоловнаМатематика, Геометрія, Статистика → Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій - Реферат

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

ставить у вiдповiднiсть V-квазиарну функцію f, значення f(d) якої для кожного d VN визначається як перший елемент аm послiдовностi a0= d(v), a1=f(d vaa0), a2=f(d vaa1), ..., ak=f(d vaak-1), ... такий, що (d vaam)=0 та для всiх ky програмований.
Справдi, такий предикат моделюється функцiєю .
Приклад 5. Предикати x y, x=y та x y програмовані.
Предикат x y моделюється функцiєю ; предикат x=y моделюється функцiєю 1-|x-у|, його ж можна подати у вигляді (x y)&(y x); предикат x у можна подати у вигляді (x=у) або у вигляді (x>y) ( у>х).
Приклад 6. Функцію +xy можна отримати із базових функцій о, sх, 'v, xy за допомогою операцій N?v та S .
Маємо zПриклад 7. Операцiю розгалуження N можна промоделювати, використовуючи базові функції ППА-EQ-N і операції суперпозицiї та циклу. Справдi, нехай f =N ( , g, h). Тодi f=g sg( )+h nsg( ).
Отже, функцiю +xy можна не включати до базових програмованих на N V-квазиарних функцiй; функцію N ( , g, h) можна отримати iз базових функцiй о, sх, 'v, xy , та функцiй , g i h за допомогою операцiй N?v та S .
Приклад 8. Функції min(x, y) та max(x, y) програмовані.
Справді, функції min(x, y) та max(x, y) можна подати відповідно операторними термами N ( , 'у, 'х) та N ( , 'х, 'у). Такі терми відповідно позначатимемо mіпxy та mахxy .
Приклад 9. Функція mod(x, y) програмована.
Справді, функцію mod(x, y) можна подати операторним термом N?х(Sх( , sх), ). Такий терм позначимо modxy .
Приклад 10. Функція програмована.
Справді, функцію можна подати операторним термом Sу(N?у(Su,v( , sх, Su,v( uv, sy, sy), sy), 0).
Приклад 11. Функція [x, y] програмована.
Справді, функцію [x, y] можна подати операторним термом Sz(N?z(Su,v( , sх, Su( uy, sz), sz), 0).
Приклад 12. Функція HCK(x, y) програмована.
Справді, функцію HCK(x, y) можна подати операторним термом Sz(N?z(Su,v(+uv, modzx, modzy), sz), maxxy).
Приклад 13. Функція HCD(x, y) програмована.
Справді, функцію HCD(x, y) можна подати операторним термом Sz(N?z(Su,v(+uv, modxz, modyz), Su( , 1), minxy).
Для випадку п-арних функцій N операцiї суперпозицiї, циклу та розгалуження уточнимо наступним чином..
Операцiя N? n-арним функціям g та ставить у вiдповiднiсть n-арну функцiю f, значення f(x1, ..., xn) якої для кожного набору значень x1, ..., xn визначається як перший елемент аm послiдовностi a0=x1, a1=f(a0, x2, ..., xn), a2=f(a1, x2, ..., xn), ..., ak=f(ak-1, x2, ..., xn), ... такий, що (am, x2,..., xn)=0 та для всiх kx2, x1 x2, x1=x2 та x1 x2 програмовані.
Предикат x1>x2 моделюється функцiєю . Предикат x1 x2 моделюється функцiєю , предикат x1=x2 можна подати у вигляді (x1 x2)&(x2 x1), предикат x1 x2 можна подати у вигляді (x1=x2).
Приклад 18. Функція mod(x1, x2) програмована.
Справді, функцію mod(x1, x2) можна подати операторним термом N?(S3( , S2(s, I ), I ), ).
Приклад 19. Функцiю x1+x2 можна отримати із базових функцій о, s, I , за допомогою операцій N? та Sn+1.
Позаяк x1Приклад 20. Аналогічно випадку V-квазиарних функцій, функцію f=N ( , g, h) можна подати у вигляді f=g sg( )+h nsg( ). Отже, операцiю розгалуження N можна промоделювати, використовуючи базові функції о, s, 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док випливає:
клас РФ спiвпадає з класом тотальних АОФ, заданих на множинi натуральних чисел.
Значення тези Чорча (скорочено ТЧ) полягає в наступному.
1) Прийняття тези Чорча перетворює iнтуїтивнi поняття алгоритму, обчислюваностi, розв'язностi в об'єкти математичного вивчення.
2) Використання тези Чорча як своєрiдної аксiоми дозволяє в багатьох випадках замiнити формальнi завдання алгоритмiв на неформальнi їх описи. Це дає iстотне спрощення доведень, звiльняючи його вiд зайвих деталей. Проте доведення на основi тези Чорча має бути ретельно аргументованим! При виникненнi сумнiвiв треба вміти провести чисто формальне доведення.
Розглянемо приклад використання тези Чорча. Нехай функція f є ЧРФ. Доведемо, що функція h(x)= теж є ЧРФ. Для цього розглянемо процес глобального обчислення всіх значень функції f. Такий процес розіб'ємо на етапи. На кожному етапіпочинаємо обчислення для наступного значення аргументу. На етапі 0 робимо 1-й крок обчислення f(0). На етапі 1 робимо 1-й крок обчислення f(1) та 2-й крок обчислення f(0) і т.д. На етапі п робимо 1-й крок обчислення f(п), 2-й крок обчислення f(п-1), … , (п+1)-й крок обчислення f(0). Якщо на якомусь етапі обчислення певного f(т) завершується, порівнюємо f(т) та х. При умові f(т)=х процес глобальних обчислень завершується, адже тоді х Ef , тому результатом нашої роботи буде число 1. При умові f(т) х продовжуємо процес глобальних обчислень. Таким чином, описано алгоритм для обчислення функції h(x), звідки за тезою Чорча функція h(x) є ЧРФ.
Loading...

 
 

Цікаве