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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
[перевірена версія][перевірена версія]
м
 
(Не показано 24 проміжні версії 3 користувачів)
Рядок 1: Рядок 1:
'''Нормальні алгоритми ''' (нормальні алгоритми) — вербальні [[алгоритм]]и, тобто, алгоритми, що перетворюють слова деякого (фіксованого) [[алфавіт]]у. Поняття нормального алгоритму введене радянським математиком [[Марков Андрій Андрійович (молодший)|А. А. Марковим]].
+
'''Нормальні алгоритми Маркова (нормальні алгорифми)''' — формалізація поняття алгоритму, що являє собою систему послідовних застосувань підстановок до слів певного алфавіту, введена математиком [[Марков Андрій Андрійович (молодший)|А. А. Марковим]] у 1956-му році. Доведено що нормальні алгоритми [[Повнота за Тюрингом|повні за Тюрингом]], тобто можуть описувати всі алгоритми що можуть виконуватись будь-яким комп'ютером.
 
'''Нормальний алгоритм Маркова''' — система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті.
 
   
 
== Визначення нормального алгоритму ==
 
== Визначення нормального алгоритму ==
  +
Будь-який нормальний алгоритм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгоритму. Алфавітом нормального алгоритму може бути довільний скінченний алфавіт ''A''.
   
Будь-який нормальний алгоритм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгоритму. Алфавітом нормального алгоритму може бути довільний скінченний алфавіт ''A''. Формулами підстановок в алфавіті ''A'' називаються вирази подібні ''p'' → ''q'' (проста пістановка) або ''p'' →• ''q'' (кінцева підстановка), де ''p'' та ''q'' — деякі слова в алфавіті ''A'', які називаються лівою та правою частинами формули відповідно (вважається, що алфавіт ''A'' не містить символів → та →•).
+
Схемою нормального алгоритму називають список формул підстановок цього алгоритму. Формулами підстановок в алфавіті ''A'' називаються вирази подібні ''p'' → ''q'' (проста підстановка) або ''p'' →• ''q'' (заключна підстановка), де ''p'' та ''q'' — деякі слова в алфавіті ''A'', які називаються лівою та правою частинами формули відповідно (вважається, що алфавіт ''A'' не містить символів → та →•).
 
Кожний нормальний алгоритм в алфавіті ''A'' має скінченну кількість таких формул підстановок. Їх записують у вигляді списку. Цей список називається схемою алгоритму.
 
   
 
=== Принцип дії ===
 
=== Принцип дії ===
Рядок 16: Рядок 13:
 
* З отриманим словом ''s''<sub>1</sub> повторюють попередній крок.
 
* З отриманим словом ''s''<sub>1</sub> повторюють попередній крок.
   
Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритму. Крім того, постулють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із кінцевих формул підстановки, тобто, формул виду''p'' →• ''q''. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритму до слова ''s''.
+
Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритму. Крім того, постулюють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із заключних формул підстановки, тобто, формул виду ''p'' →• ''q''. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритму до слова ''s''.
   
=== Приклад роботи ===
+
=== Перший приклад роботи ===
   
Як приклад схеми нормального алгоритму можна навести наступну схему в алфавіті з п'яти літер <tt>|*abc</tt><ref>[http://ru.wikipedia.org/w/index.php?title=%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%84%D0%BC&oldid=2992153 Нормальный алгоритм] (рос.), Википедия, 26 січня 2007.</ref>:
+
Як приклад схеми нормального алгоритму можна навести наступну схему в алфавіті з п'яти літер <tt>|*abc</tt>, яка реалізовує унарне множення:
   
 
<math>\left\{\begin{matrix}
 
<math>\left\{\begin{matrix}
Рядок 46: Рядок 43:
 
# <math>c||</math>,
 
# <math>c||</math>,
 
# <math>||</math>.
 
# <math>||</math>.
Результатом застосування буде слово <math>||</math>.
+
Результатом застосування буде слово <math>||</math>, що узгоджується з <math>|*|| = ||</math>.
   
  +
=== Другий приклад роботи ===
== Можливості нормальних алгоритмів ==
 
  +
Даний алгоритм перетворює [[Двійкова система числення|двійкові числа]] в «<nowiki/>[[Унарна система числення|унарні]]<nowiki/>» (в яких записом цілого невід'ємного числа N є рядок з N паличок). Наприклад, двійкове число 101 перетвориться в 5 паличок: |||||.
   
  +
==== Алфавіт ====
Доведено, що відносно виконуваних перетворень, нормальні алгоритми збігаються з іншими класами алгоритмів, введених для уточнення інтуїтивного поняття алгоритму, наприклад, з [[Машина Тюринга|машинами Тюринга]].
 
  +
{ 0, 1, | }.
   
  +
==== Правила ====
Аналог [[Чорча теза|тези Чорча]] для нормальних алгорифмів є такий принцип нормалізації А.&nbsp;А.&nbsp;Маркова: будь-який алгорифм в алфавіті ''A'' достатньо еквівалентний відносно ''A'' деякому нормальному алгорифма над ''A''.
 
   
  +
# 1 → 0|,
Визначення алгоритмів у нормальному вигляді дуже схоже на [[числення]], і це є дуже корисним у випадках, коли поняття числення в досліджуваному розділі [[математика|математики]] або [[кібернетика|кібернетики]] широко застосовують, як, приміром, в [[логіка математична|математичній логіці]] або в [[лінгвістика математична|математичній лінгвістиці]].
 
  +
# |0 → 0||,
  +
# 0 → (порожній рядок).
   
  +
==== Покрокове виконання алгоритму ====
Використовуючи поняття нормального алгоритма, Марков та інші дослідники довели нерозв'язність цілого набору алгоритмічних проблем.
 
  +
При застосуванні алгоритму з наведеною вище схемою до слова 101 будуть отримуватись слова:
   
  +
# 0|01,
== Джерела інформації ==
 
  +
# 0|00|,
* [[Енциклопедія кібернетики]], т. '''2''', c. 90—91.
 
  +
# 00||0|,
  +
# 00|0|||,
  +
# 000|||||,
  +
# 00|||||,
  +
# 0|||||,
  +
# |||||.
   
  +
== Можливості нормальних алгоритмів ==
=== Посилання ===
 
* [http://yad-studio.github.io/ Yad Studio&nbsp;— IDE та інтерпритатор для Нормальних Алгоритмів Маркова (Open Source)]
 
<references />
 
   
  +
Доведено, що відносно виконуваних перетворень, нормальні алгоритми збігаються з іншими класами алгоритмів, введених для уточнення інтуїтивного поняття алгоритму, наприклад, з [[Машина Тюринга|машинами Тюринга]].
== Див. також ==
 
* [[Машина Тюринга]]
 
* [[Лямбда числення]]
 
* [[Числення Поста]]
 
* [[Нерозв'язні алгоритмічні проблеми]]
 
   
  +
Аналог [[Чорча теза|тези Чорча]] для нормальних алгорифмів є такий принцип нормалізації А.&nbsp;А.&nbsp;Маркова: будь-який алгорифм в алфавіті ''A'' достатньо еквівалентний відносно ''A'' деякому нормальному алгорифма над ''A''.
=== Література ===
 
* ''Марков А. А.'' Теория алгорифмов. «Труды математического ин-та им. В.&nbsp;А.&nbsp;Стеклова АН СССР», 1954, т. 42. {{ref-ru}}
 
* ''Марков А. А., Нагорный Н. М.'' Теория алгорифмов.&nbsp;— М.: Наука, 1984.&nbsp;— 432 с. {{ref-ru}}
 
   
  +
Визначення алгоритмів у нормальному вигляді дуже схоже на [[числення]], і це є дуже корисним у випадках, коли поняття числення в досліджуваному розділі [[математика|математики]] або [[кібернетика|кібернетики]] широко застосовують, як, приміром, в [[логіка математична|математичній логіці]] або в [[лінгвістика математична|математичній лінгвістиці]].
{{math-stub}}
 
[[Категорія:Теорія алгоритмів]]
 
 
 
{{Приєднати до|Нормальні алгорифми}}
 
'''Нормальний алгоритм Маркова'''&nbsp;— система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті. У 1956 році математиком А.&nbsp;А.&nbsp;Марковим було запропоновано нове уточнення поняття алгоритму, яке пізніше було названо його ім'ям.
 
 
== Нормальні Алгоритми Маркова. Побудова алгоритмів з алгоритмів ==
 
В запропонованому марковим уточненні виділені 7 параметрів були визначені таким чином:
 
* Сукупність початкових даних&nbsp;— слова в алфавіті S;
 
* Сукупність можливих результатів&nbsp;— слова в алфавіті W;
 
* Сукупність можливих проміжних результатів&nbsp;— слова в алфавіті
 
* Р = SWV, де V&nbsp;— алфавіт службових допоміжних символів.
 
P *&nbsp;— безліч слів над алфавітом Р, n називається правилом підстановки. Сенс цього правила полягає в тому, що оброблюване слово w є видимим зліва направо і шукається входження в нього слова a. Слово a називається входженням в слово w, якщо існують такі слова b і n над тим же алфавітом, що і a і w, для яких вірно: w = ban. Якщо входження a в w знайдено, то слово a замінюється на слово g. Всі правила постановки упорядковуються. Спочатку шукається входження для першого правила підстановки. Якщо воно знайдено, то відбувається підстановка і перетворюване слово знову проглядається зліва направо у пошуках входження. Якщо входження для першого правила не знайдено, то шукається входження для другого правила і&nbsp;т.&nbsp;д. Якщо входження знайдено для n-го правила підстановки, то відбувається підстановка, і перегляд правил починається з першого, а слово проглядається спочатку і зліва направо. Вся сукупність правил підстановки називається схемою алгоритму.
 
 
== Визначення нормального алгоритму ==
 
Будь-який нормальний алгоритм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгоритму. Алфавітом нормального алгоритму може бути довільний скінченний алфавіт ''A''. Формулами підстановок в алфавіті ''A'' називаються вирази подібні ''p'' → ''q'' (проста пістановка) або ''p'' →• ''q'' (кінцева підстановка), де ''p'' та ''q''&nbsp;— деякі слова в алфавіті ''A'', які називаються лівою та правою частинами формули відповідно (вважається, що алфавіт ''A'' не містить символів → та →•).
 
 
Кожний нормальний алгоритм в алфавіті ''A'' має скінченну кількість таких формул підстановок. Їх записують у вигляді списку. Цей список називається схемою алгоритму.
 
 
== Принцип дії ==
 
Застосування нормального алгоритму до слова ''s'' полягає в наступному.
 
 
* В заданому списку формул підстановок знаходять першу формулу, ліва частина якої входить до слова ''s''. Знаходять перше входження цієї частини в слові ''s'' і замість цього входження підставляють праву частину формули. Це дасть нове слово ''s''<sub>1</sub>.
 
* З отриманим словом ''s''<sub>1</sub> повторюють попередній крок.
 
 
Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритму. Крім того, постулюють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із кінцевих формул підстановки, тобто, формул виду''p'' →• ''q''. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритму до слова ''s''.
 
 
== Приклад роботи ==
 
Як приклад схеми нормального алгоритму можна навести наступну схему в алфавіті з п'яти літер <tt>|*abc</tt><ref>[http://ru.wikipedia.org/w/index.php?title=%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%84%D0%BC&oldid=2992153 Нормальный алгоритм] (рос.), Википедия, 26 січня 2007.</ref>:
 
 
<math>\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.</math>
 
 
При застосуванні алгоритму з наведеною вище схемою до слова <math>|*||</math> будуть отримуватись слова:
 
# <math>|b*|</math>,
 
# <math>ba|*|</math>,
 
# <math>a|*|</math>,
 
# <math>a|b*</math>,
 
# <math>aba|*</math>,
 
# <math>baa|*</math>,
 
# <math>aa|*</math>,
 
# <math>aa|c</math>,
 
# <math>aac</math>,
 
# <math>ac|</math>
 
# <math>c||</math>,
 
# <math>||</math>.
 
Результатом застосування буде слово <math>||</math>.
 
 
== Теореми та приклади ==
 
* Правило початку&nbsp;— проглядання правил завжди починається з першого.
 
* Правило закінчення&nbsp;— виконання алгоритму закінчується, якщо:
 
# було застосовано правило підстановки виду aag,
 
# не застосовно жодне правило підстановки зі схеми алгоритму.
 
* Правило розміщення результату&nbsp;— слово, отримане після закінчення виконання алгоритму.
 
 
=== Побудувати алгоритм для обчислення. ===
 
U (n) = n +1;
 
 
S = {0,1,2,3,4,5,6,7,8,9}; S = W; V = {*, +}.
 
 
Переганяти службовий символ * в кінець слова n, щоб відзначити останню цифру молодших розрядів. Збільшуємо на одиницю, починаючи з цифр молодших розрядів. Вводимо службовий символ * в слово, щоб їм відзначити останню цифру в слові. Схема НАМ для обчислення U 1 (n) = n +1. Неважко зміркувати, що складність цього алгоритму, виражена в кількості виконаних правил підстановки, буде дорівнює: (k +1) + (l +1), де k&nbsp;— кількість цифр в n, l&nbsp;— кількість 9, які були збільшені на 1. Але в будь-якому випадку складність НАМ для U 1 (n) більше складності Машини Тюрінга для цієї ж функції, яка дорівнювала k +1. Зверніть увагу, що у НАМ порядок слідування правил підстановки в схемі алгоритму істотно впливає на результат, в той час як для МТ він не суттєво.
 
 
=== Побудувати алгоритм для обчислення. ===
 
U 2 ((n) 1) = (n-1) 1
 
 
Отже, S = {|}; W = S; V = Г†, тобто порожньо. Складність цього алгоритму рівна 1, у той час як складність алгоритму для Машини Тюрінга дорівнювала n.
 
 
=== Побудувати алгоритм для обчислення. ===
 
U 3 ((n) 1) = (n) 10
 
 
S = {|}; W = {0,1,2,3,4,5,6,7,8,9}; V = Г
 
 
Складність цього НАМ буде n + [log 10 n], що істотно менше складності для Машини Тюрінга, обчислює цю функцію, яка дорівнювала n 2 + [log 10 n (log 10 n +1)]. Реалізацію функції U 4 порівняння двох цілих чисел залишаємо читачу як вправи. Зауваження: початкове слово треба задати в формі *. Для нормальних алгоритмів Маркова справедлива теза, аналогічний тези Тьюринга. Теза Маркова: Для будь інтуїтивно обчислюваною функції існує алгоритм, її обчислює. Побудова алгоритмів з алгоритмів. Дотепер, будуючи ту чи іншу МТ, або НАМ ми кожного разу всі робили наново. Природно поставити запитання, а чи не можна при побудові, наприклад, нової МТ користуватися вже побудованою раніше МТ. МТ 3 з прикладу. U 3 ((n) 1) = (n) 10 по суті є належним чином об'єднані МТ для U 1 (n) = n +1 і U 2 ((n) 1) = (n-1) 1 . Аналогічне питання можна сформулювати для НАМ. Іншими словами чи можна акумулювати знання у формі алгоритмів так, щоб з них можна було будувати інші алгоритми. Ми розглянемо цю проблему стосовно до МТ. Однак всі сформульовані нами твердження будуть справедливі і для НАМ і для інших еквівалентних уточнень поняття алгоритму. Еквівалент уточнень поняття алгоритму ми розглянемо пізніше. Будемо говорити, що МТ 1 можна ефективно побудувати з МТ 2 і МТ 3 якщо існує алгоритм, який дозволяє, маючи програму для МТ 2 і МТ 3 , побудувати програму для МТ 3. Послідовною композицією МТ А і В називається така МТ З, що область застосовності МТ А і С збігаються; C (a) = B (A (a)). Іншими словами, застосування З до слова a дає такий же результат, як послідовне застосування до цього ж слова спочатку А, а потім до результату застосування А&nbsp;— В. Послідовну композицію МТ А і МТ В будемо позначати АoВ.
 
 
'''Теорема.'''
 
 
Нехай дано МТ А і В, такі, що В застосовна до результатів роботи А і Q A Q B = Г. Тоді можна ефективно побудувати МТ З таку, що С = АoВ.
 
 
'''Доказ.'''
 
 
Як алфавіт даних і множину станів для МТ З візьмемо об'єднання алфавітів даних і множин станів для А і В, тобто D C = D A D В, Q C = Q A Q B. У програмі початковий стан для В. Це забезпечить включення У в той момент, коли А свою роботу закінчила і не раніше, тому Q A Q B = Г.
 
 
'''Теорема.'''
 
   
  +
Використовуючи поняття нормального алгоритму, Марков та інші дослідники довели нерозв'язність цілого набору алгоритмічних проблем.
Для будь-яких МТ А і МТ В можна ефективно побудувати МТ З таку, що С = А | | В.
 
   
'''Обґрунтування.'''
 
   
Ми не будемо давати тут строго доказу з причини його технічної складності. Покажемо лише обґрунтування правильності затвердження теореми. Позначимо D C = D A D B ; Q C = Q A Q B.
 
   
 
== Див. також ==
 
== Див. також ==
Рядок 182: Рядок 89:
 
* [[Машина Тюринга]]
 
* [[Машина Тюринга]]
 
* [[Числення Поста]]
 
* [[Числення Поста]]
  +
* [[Алгоритмічно нерозв'язна задача]]
* [[Нерозв'язні алгоритмічні проблеми]]
 
   
 
== Примітки ==
 
== Примітки ==
Рядок 188: Рядок 95:
   
 
== Література ==
 
== Література ==
  +
* [[Енциклопедія кібернетики]], т. '''2''', c. 90—91.
 
* Джон Хопкрофт, Раджів Мотані, Джеффрі Ульман РОЗДІЛ 8. Введення в теорію машин Тюрінга // Введення в теорію автоматів, мов і обчислень.&nbsp;— М., 2002.&nbsp;— С528.
 
* Джон Хопкрофт, Раджів Мотані, Джеффрі Ульман РОЗДІЛ 8. Введення в теорію машин Тюрінга // Введення в теорію автоматів, мов і обчислень.&nbsp;— М., 2002.&nbsp;— С528.
  +
* {{cite book|
* ''Марков А. А.'' Теория алгорифмов. «Труды математического ин-та им. В.&nbsp;А.&nbsp;Стеклова АН СССР», 1954, т. 42.
 
  +
|last=Марков
* ''Марков А. А., Нагорный Н. М.'' Теория алгорифмов. М.: Наука, 1984.&nbsp;— 432 с.
 
  +
|first=А. А.
  +
|authorlink=Марков Андрій Андрійович (молодший)
  +
|title=Теория алгорифмов. «Труды математического ин-та им. В.&nbsp;А.&nbsp;Стеклова АН СССР»
  +
|year=1954
  +
|volume=42
  +
|url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=tm&paperid=1178&option_lang=rus
  +
|ref=harv
  +
}} {{ref-ru}}
  +
* ''Марков А. А., Нагорный Н. М.'' Теория алгорифмов.&nbsp;— М.: Наука, 1984.&nbsp;— 432 с. {{ref-ru}}
   
  +
=== Посилання ===
{{math-stub}}
 
  +
* [http://yad-studio.github.io/ Yad Studio&nbsp;— IDE та інтерпритатор для Нормальних Алгоритмів Маркова (Open Source)]
   
 
[[Категорія:Теорія алгоритмів]]
 
[[Категорія:Теорія алгоритмів]]

Поточна версія на 09:37, 11 травня 2019

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

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

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


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

Примітки[ред. | ред. код]

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

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