Визначення нормального алгоритму і його виконання

В середині минулого століття видатний російський математик А.А. Марков ввів поняття нормального алгоритму (алгорифм) з метою уточнення поняття "алгоритм", що дозволяє вирішувати задачі по визначенню алгоритмічно нерозв'язних проблем. Пізніше це поняття отримало назву нормального алгоритму Маркова (НАМ). Мова НАМ, з одного боку, навмисно бідна, що необхідно для мети введення поняття "алгоритм". Однак, з іншого боку, ідеї НАМ покладені в основу великої групи мов програмування, що одержали назву мови логічного програмування.

Для визначення НАМ вводиться довільний алфавіт - кінцеве непорожня множина символів, за допомогою яких описується алгоритм і дані. В алфавіт також включається порожній символ, який ми будемо позначати грецькою буквою. Під словом розуміється будь-яка послідовність непустих символів алфавіту або порожній символ, який позначає порожнє слово.

Всякий НАМ визначається кінцевою впорядкованою множиною пар слів алфавіту, названих підстановками. У парі слів підстановки ліве (перше) слово непорожній, а праве (друге) слово може бути порожнім символом. Для наочності ліве і праве слово розділяються стрілкою.

В якості даних алгоритму береться будь-яка непорожній рядок символів. Робота НАМ складається з послідовності абсолютно однотипних кроків. Крок роботи алгоритму може бути описаний таким чином: 1.У впорядкованої послідовності підстановок шукаємо найпершу підстановку, ліве слово якої входить в рядок даних. 2.У рядку даних шукаємо найперше (ліве) входження лівого слова знайденої підстановки. 3.Це входження в рядку даних замінюємо на праве слово знайденої підстановки (перетворення даних).

Крок роботи алгоритму повторюється до тих пір, поки

• або не виникне ситуація, коли крок не зможе бути виконаний через те, що жодна підстановка не підходить (ліве слово підстановки вже не входить в рядок даних) - правило зупинки;
• або не буде встановлено, що процес підстановок не може зупинитися.

У першому випадку рядок даних, що вийшла, при зупинці алгоритму, є вихідний (результатом) і алгоритм застосуємо до вхідних даних, а в другому випадку алгоритм не застосуємо до вхідних даних.