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

q3 q0R

q2# q*|

q0# q4R

q4| q4R (єдина відмінність від МТ для f(x, y) =x-y )

q4 q*

Приклад 4. МТ, яка обчислює функцiю f(x)=sg(x):

q0 q*

q0| q1|R

q1| q1R

q1 q*

Приклад 5. МТ, яка обчислює предикат "x парне":

q0| q1R

q1| q0R

q0 q*|

q1 q*

3. НОРМАЛЬНІ АЛГОРИТМИ МАРКОВА

Пiд нормальним алгоритмом (скорочено НА) в алфавiтi T розумiють впорядковану послiдовнiсть продукцiй (правил) вигляду або , де T* та T. Продукцiї вигляду називають фiнальними.

Кожен НА в алфавiтi T задає деяке вербальне вiдображення T*→T*. Слово, яке є результатом обробки слова x нормальним алгоритмом A, позначимо A(x). Обробка слова x нормальним алгоритмом A проводиться поетапно таким чином.Покладемо x0=x i скажемо, що x0 отримане iз x пiсля 0 етапiв. Нехай слово xn отримане iз слова x пiсля n етапiв. Тодi (n+1)-й етап виконується так.

Шукаємо першу за о порядком продукцiю або таку, що пiдслово xn. Застосуємо цю продукцiю до xn , тобто замiнимо в xn найлiвiше входження на . Отримане слово позначимо xn+1. Якщо застосована на (n+1)-му етапi продукцiя нефiнальна, тобто, то переходимо до (n+2)-го етапу. Якщо ця продукцiя фiнальна, тобто , то пiсля її застосування A зупиняється i A(x)=xn+1. Якщо ж на (n+1)-му етапi жодна продукцiя A не застосовна до xn+1, тобто в A немає продукцiї, лiва частина якої - пiдслово слова xn+1, то A зупиняється i A(x)=xn.

Якщо в процесi обробки слова x НА A не зупиняється нi на якому етапi, то вважаємо, що A(x) невизначене.

Нормальний алгоритм називають нормальним алгоритмом над алфавiтом T, якщо вiн є нормальним алгоритмом в деякому розширеннi T’T. НА над T задає певне вiдображення T*→T*, використовуючи в процесi обробки слiв допомiжнi символи поза алфавiтом T. Зупинка НА A над T при роботі над словом хT*, результативна, коли вона вiдбулась на словi yT*, iнакше вважаємо, що результат роботи A над х невизначений.