Нормальный алгорифм - meaning and definition. What is Нормальный алгорифм
Diclib.com
ChatGPT AI Dictionary
Enter a word or phrase in any language 👆
Language:

Translation and analysis of words by ChatGPT artificial intelligence

On this page you can get a detailed analysis of a word or phrase, produced by the best artificial intelligence technology to date:

  • how the word is used
  • frequency of use
  • it is used more often in oral or written speech
  • word translation options
  • usage examples (several phrases with translation)
  • etymology

What (who) is Нормальный алгорифм - definition

Нормальные алгоритмы Маркова; Алгоритм Маркова; Алгорифмы Маркова; Нормальный алгорифм Маркова; Нормальный алгоритм Маркова; Автомат Маркова; Алгорифм Маркова; Нормальный алгорифм

Нормальный алгорифм         

одно из современных уточнений понятия Алгоритма, получившее распространение в исследованиях по конструктивной математике (См. Конструктивная математика). Предложено в 1950 А. А. Марковым, впервые систематически и строго построившим на основе этого уточнения общую алгоритмов теорию (См. Алгоритмов теория). Н. а. эквивалентны частично-рекурсивным функциям (см. Рекурсивные функции), а следовательно, и Тьюринга машинам.

Концепция Н. а. специально приспособлена для реализации алгоритмов, действующих над словами в тех или иных алфавитах. При этом под алфавитом в математике понимается любой конечный набор четко отличимых друг от друга графических символов (букв), а под словом в данном алфавите - произвольная конечная цепочка букв этого алфавита. Цепочка, вовсе не содержащая букв, также считается словом в данном алфавите (пустое слово). Например, цепочки "ииаам", "книга", "гамма" являются словами в русском алфавите, а также в шестибуквенном алфавите {к, н, и, г, а, м}. Элементарным актом преобразования слов в алгоритмических процессах, задаваемых Н. а., является т. н. операция "подстановки вместо первого вхождения". Пусть Р, Q, R - слова в некотором алфавите. Результатом подстановки Q вместо первого вхождения Р в R называется слово ∑ (R, Р, Q), получаемое следующим образом. Если Р входит в R, т.е. R представимо в виде S1PS2, то среди таких представлений отыскивается представление с наиболее коротким словом S1 и полагается ∑ (R, Р, Q) = S1QS2. Если же Р не входит в R, то ∑ (R, Р, Q) = R. Так, ∑ (гамма, а, е) = гемма.

Для задания Н. а. необходимо фиксировать некоторый алфавит А, не содержащий букв "→" и " · ", и упорядоченный список слов вида РQ (простая формула подстановки) или Р · Q (заключит. формула подстановки), где Р и Q - слова в А. Формулы подстановок принято записывать друг под другом в порядке следования, объединяя их слева фигурной скобкой. Получающаяся фигура называется схемой Н. а. Исходными данными и результатами работы Н. а. являются слова в А (сам Н. а. называется Н. а. в алфавите А). Процесс применения к слову R Н. а. со схемой вида

где δi (1 ≤ i n) означает "→" или "→", разворачивается следующим образом. Отыскивается наименьшее i, при котором Pi входит в R. Если все Pi не входят в R, то работа заканчивается и её результатом считается R. Если требуемое i найдено, то переходят к слову ∑ (R, Pi, Qi). При этом в случае, если использованная формула подстановки PiδiQi была заключительной (δi = → ), работа заканчивается и результатом считается ∑ (R, Pi, Qi). Если же формула PiδiQi - простая, то описанная процедура повторяется с заменой R на ∑ (R, Ri, Qi).

Пример. Натуральные числа можно рассматривать как слова в алфавите {О, 1} вида 0, 01, 01l,... Н. а. в этом алфавите со схемами {0 → · 01 и {1→ переводят каждое натуральное число п соответственно в n + 1 и в 0.

Множество всех Н. а. замкнуто относительно известных способов комбинирования алгоритмов. Например, по любым двум Н. а. и можно построить Н. а. , являющийся композицией и , т. е. реализующий следующий интуитивный алгоритм: "сначала выполнить алгоритм , затем к результату применять ".

Соотношение между интуитивными алгоритмами и Н. а. описывается выдвинутым А. А. Марковым принципом нормализации: всякий алгоритм, перерабатывающий слова в данном алфавите А в слова в этом же алфавите, может быть реализован посредством Н. а. в некотором расширении А. [Легко указать очень простые алгоритмы в А, не реализуемые Н. а. в A; с другой стороны, всегда можно ограничиться двухбуквенным (и даже однобуквенным) расширением A.] Принцип нормализации эквивалентен тезису Чёрча и, аналогично последнему, не может быть доказан из-за неточности интуитивной концепции алгоритма.

Лит.: Марков А. А., Теория алгорифмов, М. - Л., 1954 (Тр. Математического института АН СССР, т. 42); Мендельсон Э., Введение в математическую логику, пер. с англ., М., 1971.

Б. А. Кушнер.

Нормальный алгоритм         
Норма́льный алгори́тм (алгори́фм) Ма́ркова (НАМ, также марковский алгоритм) — один из стандартных способов формального определения понятия алгоритма (другой известный способ — машина Тьюринга). Понятие нормального алгоритма введено А.
Нормальный делитель         

инвариантная подгруппа, одно из основных понятий теории групп (См. Группа), введённое Э. Галуа. Н. д. группы G - подгруппа Н, для которой gH = Hg при любом выборе элемента g группы G.

Wikipedia

Нормальный алгоритм

Норма́льный алгори́тм (алгори́фм) Ма́ркова (НАМ, также марковский алгоритм) — один из стандартных способов формального определения понятия алгоритма (другой известный способ — машина Тьюринга). Понятие нормального алгоритма введено А. А. Марковым (младшим) в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики на механико-математическом факультете МГУ.

Нормальный алгоритм описывает метод переписывания строк, похожий по способу задания на формальные грамматики. НАМ — полный по Тьюрингу язык, что делает его по выразительной силе эквивалентным машине Тьюринга и, следовательно, современным языкам программирования. На основе НАМ был создан функциональный язык программирования Рефал.