Нормальні алгоритми Маркова

Нормальні алгоритми Маркова (нормальні алгорифми) — формалізація поняття алгоритму, що є системою послідовних застосувань підстановок до слів певного алфавіту, введена математиком А. А. Марковим у 1956 році. Доведено, що нормальні алгоритми повні за Тюрінгом, тобто можуть описувати всі алгоритми, що можуть виконуватись будь-яким комп'ютером.

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

Будь-який нормальний алгоритм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгоритму. Алфавітом нормального алгоритму може бути довільний скінченний алфавіт A.

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

Принцип дії

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

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

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

Перший приклад роботи

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

${\displaystyle \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.}$

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

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

Результатом застосування буде слово ${\displaystyle ||}$, що узгоджується з ${\displaystyle |*||=||}$.

Другий приклад роботи

Даний алгоритм перетворює двійкові числа в «унарні» (в яких записом цілого невід'ємного числа N є рядок з N паличок). Наприклад, двійкове число 101 перетвориться в 5 паличок: |||||.

Алфавіт

{ 0, 1, | }.

Правила

1. 1 → 0|,
2. |0 → 0||,
3. 0 → (порожній рядок).

Покрокове виконання алгоритму

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

1. 0|01,
2. 0|00|,
3. 00||0|,
4. 00|0|||,
5. 000|||||,
6. 00|||||,
7. 0|||||,
8. |||||.

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

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

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

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

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

Див. також

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

Примітки

Література

• (укр.) Формальні мови та алгоритмічні моделі. — І.-Ф.  : Голіней, 2023. — 180 с.
• Енциклопедія кібернетики, т. 2, c. 90—91.
• Hopcroft, John E.; ; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
• Марков, А. А. (1954). . Т. 42. Архів оригіналу за 19 лютого 2018. Процитовано 18 лютого 2018. (рос.)
• Марков А. А., Нагорный Н. М. Теория алгорифмов. — М.: Наука, 1984. — 432 с. (рос.)

Посилання

• Yad Studio — IDE та інтерпритатор для Нормальних Алгоритмів Маркова (Open Source) [ 17 березня 2014 у Wayback Machine.]