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

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

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

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