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

Нормальный алгорифм
        одно из современных уточнений понятия Алгоритма, получившее распространение в исследованиях по конструктивной математике (См. Конструктивная математика). Предложено в 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.
         Б. А. Кушнер.

Большая советская энциклопедия. — М.: Советская энциклопедия. 1969—1978.

Смотреть что такое "Нормальный алгорифм" в других словарях:

  • Нормальный алгорифм — Нормальный алгоритм Маркова один из стандартизованных вариантов представления об алгорифме (алгоритме). Понятие нормального алгоритма введено А. А. Марковым в конце 1940 х годов. Содержание 1 Описание 2 Примеры 2.1 Пример 1 2.2 …   Википедия

  • НОРМАЛЬНЫЙ АЛГОРИФМ — алгорифм преобразования слов в нек ром конкретном алфавите (при этом слово рассматривается как общая форма конструктивного объекта). Всякий Н. а. вполне определяется заданием алфавита, в к ром он действует, и списка формул подстановок (схем) в… …   Философская энциклопедия

  • НОРМАЛЬНЫЙ АЛГОРИФМ — название, закрепившееся за алгоритмами некоторого точно охарактеризованного типа. Наряду с рекурсивными функциями и Тьюринга машинами Н. а. получили известность в качестве одного из наиболее удобных уточнений общего интуитивного представления об… …   Математическая энциклопедия

  • Нормальный алгорифм Маркова — Нормальный алгоритм Маркова один из стандартизованных вариантов представления об алгорифме (алгоритме). Понятие нормального алгоритма введено А. А. Марковым в конце 1940 х годов. Содержание 1 Описание 2 Примеры 2.1 Пример 1 2.2 …   Википедия

  • УНИВЕРСАЛЬНЫЙ НОРМАЛЬНЫЙ АЛГОРИФМ — нормальный алгорифм (н. а.) к рый в уточненном ниже смысле моделирует работу любого н. а. в алфавите A ={a1, . .., а п}.Н. а. в алфавите (. не содержит букв является универсальным для алфавита А, если для всякого н. а. в алфавите Аи для каждого… …   Математическая энциклопедия

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

  • Нормальный алгоритм Маркова — один из стандартизованных вариантов представления об алгорифме (алгоритме). Понятие нормального алгоритма введено А. А. Марковым в конце 1940 х годов. Содержание 1 Описание 2 Примеры 2.1 Пример 1 2.2 …   Википедия

  • алгоритм (алгорифм) — (от Algorithmi латинизированная форма имени выдающегося среднеазиатского ученого Аль Хорезми) конечный набор правил, позволяющих чисто механически решать любую конкретную задачу из некоторого класса однотипных задач. Примерами простейших А. могут …   Словарь терминов логики

  • Алгоритм —         алгорифм, одно из основных понятий (категорий) математики, не обладающих формальным определением в терминах более простых понятий, а абстрагируемых непосредственно из опыта. А. являются, например, известные из начальной школы правила… …   Большая советская энциклопедия

  • АЛГОРИТМ, — алгорифм, Ч точное предписание, к рое задает вычислительный процесс (называемый в этом случае алгоритмическим), начинающийся с произвольного исходного данного (из нек рой совокупности возможных для данного А. исходных данных) и направленный на… …   Математическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»