Нормальные алгорифмы Маркова

Нормальним алг. М в алф. Аназив. наступне правило побудови послідовності слів [pic 1][pic 2] в алф. А, виходячи з заданого слова V в цьому ж алфавіті.

В якості початкового слова [pic 3][pic 4] послідовності береться слово V.

Нехай для деякого і≥0, слово [pic 5][pic 6] побудовано і процес побудови, що розглядається ще не закінченій. Якщо при цьому в схемі нормального алг. немає формул, ліві частини якої входили у [pic 7][pic 8], то [pic 9][pic 10]і процес побудови послідовності вважають завершеним.

Якщо в схемі є формула з лівими частинами, які входять у [pic 11][pic 12], то в якості [pic 13][pic 14] береться результат підстановки М. правої частини першої з таких формул замість першого входження її лівої частини в слово [pic 15][pic 16].

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

Якщо процес побудови послідовності [pic 17][pic 18], і=1, 2 … m обривається, то говорять, що нормальний алг., який розглядається, можна застосувати до слова V.

Говорять, що нормальний алгоритм перероблює слово V у W.

Послідовність [pic 19][pic 20] будемо записувати наступним чином: [pic 21][pic 22]>[pic 23][pic 24]>[pic 25][pic 26]>…[pic 27][pic 28].

[pic 29][pic 30]= V; [pic 31][pic 32]= W

Якщо алг. заданий у деякому алф. А, то говорять, що він є нормальним алг. на А

Функція називається обчислювальною заТюрингом, якщо існує машина Тюринга, що її обчислює, або якщо існує машина Тюринга, яка обчислює її значення для тих наборів значень аргументів, для яких функція визначена і працює нескінченно довго, якщо функція для даного набору аргументів невизначена. Тут є декілька зауважень. По-перше, ми розглядаємо функції, що задаються на множині натуральних чисел і що приймають значення з множини натуральних чисел. По-друге, значення х1, х2, ..., хn аргументів фунцкії f (х1, х2, ..., хn) будемо розміщувати на стрічці у вигляді слова. По-третє, переробку вхідного слова будемо починати зі стандартного положення, при якому в стані х1 оглядається крайня одиниця слова, що розміщується праворуч. Якщо f (х1, х2, ..., хn) визначена на наборі значень аргументів, то в результаті роботи машини Тюринга на стрічці повинно бути записано послідовно f (х1, х2, ..., хn) одиниць. В противному випадку машина повинна працювати нескінченно довго. При виконанні перерахованих умов будемо говорити, що машина Тюринга обчислює дану функцію.

3.Нормально обчислювальні ф-ції. Принцип нормалізації Маркова.

як і машина Тьюринга, норм. алг. не проводить власні обчислення. Нормальний алг. перебудовує слова, замінюючи одні букви іншими по предписаним  їм правилам.

В свою чергу ми регламентуємо їм такі правила, результати яких можна інтерпретувати як обчислення.

Ф-ція f, яка задана на деякій множині слів алф. А назив. нормально обчислювальною ф-єю, якщо знайдеться таке розширення В даного алф. (А с В, В≠0) і такий нормальний алг. в алф. В, що кожне слово V в алф. А з областю визначення ф-ції f цей алг. перероблює в слово f(V).

! Нормальний алг. побудований в тому самому алф. А, тобто не потребує розширювати алф. А.

А. А. Марков висунув гіпотезу, яка отримала назву «принцип нормалізації Маркова». Згідно з цим принципом для знаходження значень ф-ції, яка задана в деякому алф., тоді і тільки тоді існує алг., коли ф-ція є нормально обчислюваною, так як і теза Черча, теза Тьюринга, принцип нормалізації Маркова не може бути доведений з матем. точки зору.

Теорема 1: Ф-ція, що є обчислювальною за Тьюрингом, є також нормально обч.

Теорема 2: Ф-ція, що є нормально обч. є також обчисл. за Тьюрингом.

Такі самі теореми сформовані для частково-рекурсивної ф-ції

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