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

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

ред.

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

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

Принцип дії

ред.

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

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

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

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

ред.

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

 

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

  1.  ,
  2.  ,
  3.  ,
  4.  ,
  5.  ,
  6.  ,
  7.  ,
  8.  ,
  9.  ,
  10.  
  11.  ,
  12.  .

Результатом застосування буде слово  , що узгоджується з  .

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

ред.

Даний алгоритм перетворює двійкові числа в «унарні» (в яких записом цілого невід'ємного числа 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.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
  • Марков, А. А. (1954). Теория алгорифмов. «Труды математического ин-та им. В. А. Стеклова АН СССР». Т. 42. Архів оригіналу за 19 лютого 2018. Процитовано 18 лютого 2018. (рос.)
  • Марков А. А., Нагорный Н. М. Теория алгорифмов. — М.: Наука, 1984. — 432 с. (рос.)

Посилання

ред.