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

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

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

Зміст

1 Визначення нормального алгоритму
- 1.1 Принцип дії
- 1.2 Приклад роботи
2 Можливості нормальних алгоритмів
3 Джерела інформації
- 3.1 Посилання
4 Дивіться також
- 4.1 Література

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

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

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

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

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

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

Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритму. Крім того, постулють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із кінцевих формул підстановки, тобто, формул виду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.$

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

$| b * |$ ,
$b a | * |$ ,
$a | * |$ ,
$a | b *$ ,
$a b a | *$ ,
$b a a | *$ ,
$a a | *$ ,
$a a | c$ ,
$a a c$ ,
$a c |$
$c | |$ ,
$| |$ .

Результатом застосування буде слово $| |$ .

[ред.] Можливості нормальних алгоритмів

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

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

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

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