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

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

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

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

Визначення нормального алгоритма[ред.ред. код]

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

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

Принцип дії[ред.ред. код]

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

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

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

Приклад роботи[ред.ред. код]

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

\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.

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

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

Джерела інформації[ред.ред. код]

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

  1. Нормальный алгоритм (рос.), Википедия, 26 січня 2007.

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

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

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