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

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

Перейти до: навігація, пошук

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

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

Зміст

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

Будь який нормальний алгорифм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгорифма. Алфавітом нормального алгорифма може бути довільний скінченний алфавіт 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 с.


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.
Особисті інструменти
Іншими мовами