Відмінності між версіями «Нормальні алгоритми»

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[неперевірена версія][перевірена версія]
Рядок 48: Рядок 48:
 
Даний алгоритм перетворює [[Двійкова система числення|двійкові числа]] в «<nowiki/>[[Унарна система числення|унарні]]<nowiki/>» (в яких записом цілого невід'ємного числа N є рядок з N паличок). Наприклад, двійкове число 101 перетвориться в 5 паличок: |||||.
 
Даний алгоритм перетворює [[Двійкова система числення|двійкові числа]] в «<nowiki/>[[Унарна система числення|унарні]]<nowiki/>» (в яких записом цілого невід'ємного числа N є рядок з N паличок). Наприклад, двійкове число 101 перетвориться в 5 паличок: |||||.
   
==== Алфавіт : ====
+
==== Алфавіт ====
 
{ 0, 1, | }.
 
{ 0, 1, | }.
   

Версія за 09:46, 16 травня 2018

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

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

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


Див. також

Примітки

Література

Посилання