|
Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритму. Крім того, постулюють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із кінцевих формул підстановки, тобто, формул виду''p'' →• ''q''. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритму до слова ''s''.
== Теореми та приклади ==
* Правило початку — проглядання правил завжди починається з першого.
* Правило закінчення — виконання алгоритму закінчується, якщо:
# було застосовано правило підстановки виду aag,
# не застосовно жодне правило підстановки зі схеми алгоритму.
* Правило розміщення результату — слово, отримане після закінчення виконання алгоритму.
=== Побудувати алгоритм для обчислення. ===
U (n) = n +1;
S = {0,1,2,3,4,5,6,7,8,9}; S = W; V = {*, +}.
Переганяти службовий символ * в кінець слова n, щоб відзначити останню цифру молодших розрядів. Збільшуємо на одиницю, починаючи з цифр молодших розрядів. Вводимо службовий символ * в слово, щоб їм відзначити останню цифру в слові. Схема НАМ для обчислення U 1 (n) = n +1. Неважко зміркувати, що складність цього алгоритму, виражена в кількості виконаних правил підстановки, буде дорівнює: (k +1) + (l +1), де k — кількість цифр в n, l — кількість 9, які були збільшені на 1. Але в будь-якому випадку складність НАМ для U 1 (n) більше складності Машини Тюрінга для цієї ж функції, яка дорівнювала k +1. Зверніть увагу, що у НАМ порядок слідування правил підстановки в схемі алгоритму істотно впливає на результат, в той час як для МТ він не суттєво.
=== Побудувати алгоритм для обчислення. ===
U 2 ((n) 1) = (n-1) 1
Отже, S = {|}; W = S; V = Г†, тобто порожньо. Складність цього алгоритму рівна 1, у той час як складність алгоритму для Машини Тюрінга дорівнювала n.
=== Побудувати алгоритм для обчислення. ===
U 3 ((n) 1) = (n) 10
S = {|}; W = {0,1,2,3,4,5,6,7,8,9}; V = Г
Складність цього НАМ буде n + [log 10 n], що істотно менше складності для Машини Тюрінга, обчислює цю функцію, яка дорівнювала n 2 + [log 10 n (log 10 n +1)]. Реалізацію функції U 4 порівняння двох цілих чисел залишаємо читачу як вправи. Зауваження: початкове слово треба задати в формі *. Для нормальних алгоритмів Маркова справедлива теза, аналогічний тези Тьюринга. Теза Маркова: Для будь інтуїтивно обчислюваною функції існує алгоритм, її обчислює. Побудова алгоритмів з алгоритмів. Дотепер, будуючи ту чи іншу МТ, або НАМ ми кожного разу всі робили наново. Природно поставити запитання, а чи не можна при побудові, наприклад, нової МТ користуватися вже побудованою раніше МТ. МТ 3 з прикладу. U 3 ((n) 1) = (n) 10 по суті є належним чином об'єднані МТ для U 1 (n) = n +1 і U 2 ((n) 1) = (n-1) 1 . Аналогічне питання можна сформулювати для НАМ. Іншими словами чи можна акумулювати знання у формі алгоритмів так, щоб з них можна було будувати інші алгоритми. Ми розглянемо цю проблему стосовно до МТ. Однак всі сформульовані нами твердження будуть справедливі і для НАМ і для інших еквівалентних уточнень поняття алгоритму. Еквівалент уточнень поняття алгоритму ми розглянемо пізніше. Будемо говорити, що МТ 1 можна ефективно побудувати з МТ 2 і МТ 3 якщо існує алгоритм, який дозволяє, маючи програму для МТ 2 і МТ 3 , побудувати програму для МТ 3. Послідовною композицією МТ А і В називається така МТ З, що область застосовності МТ А і С збігаються; C (a) = B (A (a)). Іншими словами, застосування З до слова a дає такий же результат, як послідовне застосування до цього ж слова спочатку А, а потім до результату застосування А — В. Послідовну композицію МТ А і МТ В будемо позначати АoВ.
'''Теорема.'''
Нехай дано МТ А і В, такі, що В застосовна до результатів роботи А і Q A Q B = Г. Тоді можна ефективно побудувати МТ З таку, що С = АoВ.
'''Доказ.'''
Як алфавіт даних і множину станів для МТ З візьмемо об'єднання алфавітів даних і множин станів для А і В, тобто D C = D A D В, Q C = Q A Q B. У програмі початковий стан для В. Це забезпечить включення У в той момент, коли А свою роботу закінчила і не раніше, тому Q A Q B = Г.
'''Теорема.'''
Для будь-яких МТ А і МТ В можна ефективно побудувати МТ З таку, що С = А | | В.
'''Обґрунтування.'''
Ми не будемо давати тут строго доказу з причини його технічної складності. Покажемо лише обґрунтування правильності затвердження теореми. Позначимо D C = D A D B ; Q C = Q A Q B.
== Див. також ==
|
