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

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

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

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

Зміст 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]:

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

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.

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

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

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

• Енциклопедія кібернетики, т. 2, c. 90-91.

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

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

[ред.] Дивіться також

• Машина Тюринга
• Лямбда числення
• Числення Поста
• Нерозв'язні алгоритмічні проблеми

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

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

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