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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Нормальні алгоритми Маркова (нормальна алгорифми) — формалізація поняття алгоритму, що являє собою систему послідовних застосувань підстановок до слів певного алфавіту, введена математиком А. А. Марковим у 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. .

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

Другий приклад роботи[ред. | ред. код]

Даний алгоритм перетворює двійкові числа в «унарні» (в яких записом цілого невід'ємного числа 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.

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

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


Див. також[ред. | ред. код]

Примітки[ред. | ред. код]

Література[ред. | ред. код]

Посилання[ред. | ред. код]