Нормальні алгорифми

Нормальні алгоритми (нормальні алгоритми) — вербальні алгоритми, тобто, алгоритми, що перетворюють слова деякого (фіксованого) алфавіту. Поняття нормального алгоритма введене радянським математиком А. А. Марковим.

Нормальний алгоритм Маркова — система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті.

Визначення нормального алгоритма

Будь який нормальний алгоритм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгоритма. Алфавітом нормального алгоритма може бути довільний скінченний алфавіт A. Формулами підстановок в алфавіті A називаються вирази подібні p → q (проста пістановка) або p →• q (кінцева підстановка), де p та q — деякі слова в алфавіті A, які називаються лівою та правою частинами формули відповідно (вважається, що алфавіт A не містить символів → та →•).

Кожний нормальний алгоритм в алфавіті A має скінченну кількість таких формул підстановок. Їх записуть у вигляді списку. Цей список називається схемою алгоритма.

Принцип дії

Застосування нормального алгоритма до слова s полягає в наступному.

• В заданому списку формул підстановок знаходять першу формулу, ліва частина якої входить до слова s. Знаходять перше входження цієї частини в слові s і замість цього входження підставляють праву частину формули. Це дасть нове слово s₁.
• З отриманим словом s₁ повторюють попередній крок.

Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритма. Крім того, постулють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із кінцевих формул підстановки, тобто, формул видуp →• q. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритма до слова s.

Приклад роботи

В якості прикладу схеми нормального алгоритму можна навести наступну схему в алфавіті з п'яти літер |*abc:

$\left\{\begin{matrix} |b & \to & ba| \\ ab & \to & ba \\ b & \to & \\ {*}| & \to & b* \\ {*} & \to & c \\ |c & \to & c \\ ac & \to & c| \\ c & \to\bullet & \end{matrix}\right.$

При застосуванні алгоритма з наведеною вище схемою до слова $|*||$ будуть отримуватись слова:

1. $|b*|$,
2. $ba|*|$,
3. $a|*|$,
4. $a|b*$,
5. $aba|*$,
6. $baa|*$,
7. $aa|*$,
8. $aa|c$,
9. $aac$,
10. $ac|$
11. $c||$,
12. $||$.

Результатом застосування буде слово $||$.

Можливості нормальних алгоритфів

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

Аналог тези Чорча для нормальних алгорифмів є наступний принцип нормалізації А. А. Маркова: будь який алгорифм в алфавіті A достатньо еквівалентний відносно A деякому нормальному алгорифма над A.

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

Використовуючи поняття нормального алгорифма, Марков та інші дослідники довели нерозв'язність цілого набору алгоритмічних проблем.

Джерела інформації

• Енциклопедія кібернетики, т. 2, c. 90-91.

Див. також

• Машина Тюринга
• Лямбда числення
• Числення Поста
• Нерозв'язні алгоритмічні проблеми

Література

• Марков А. А. Теория алгорифмов. «Труды математического ин-та им. В. А. Стеклова АН СССР», 1954, т. 42.
• Марков А. А., Нагорный Н. М. Теория алгорифмов. М.: Наука, 1984. – 432 с.