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

Большая Советская Энциклопедия. Статьи для написания рефератов, курсовых работ, научные статьи, биографии, очерки, аннотации, описания.


А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я 1 2 3 4 8 A L M P S T X
НА НГ НД НЕ НЁ НЗ НИ НК НО НР НС НУ НЧ НЫ НЬ НЭ НЮ НЯ
НОА
НОБ
НОВ
НОГ
НОД
НОЕ
НОЖ
НОЗ
НОИ
НОЙ
НОК
НОЛ
НОМ
НОН
НОО
НОП
НОР
НОС
НОТ
НОУ
НОЧ
НОЯ

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

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

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

  где di  (1 £i  £n)   означает «®» или «®», разворачивается следующим образом. Отыскивается наименьшее i, при котором Pi входит в R. Если все Pi не входят в R, то работа  можно построить Нормальный алгорифм , являющийся композицией  и , т. е. реализующий следующий интуитивный алгоритм: «сначала выполнить алгоритм , затем к результату применять ».

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

 

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

  Б. А. Кушнер.

 

Так же Вы можете узнать о...


Цифровая индикаторная лампа, цифровой индикатор, электровакуумный прибор для визуального воспроизведения информации (представленной в знаковой форме) в виде светящихся изображений цифр и др.
Шина (пневматич.) Шина, см. Шины пневматические.
Эндокринология (от эндо..., греч. krino — отделяю, выделяю и .
Австро-турецкие войны 16-18 вв. Австро-турецкие войны 16—18 вв. С 20-х гг. 16 в.
Аналгезия (греч. analgēsia — бесчувственность), полное исчезновение болевой чувствительности.
Афанасьев Василий Иванович (1843, Петербург, — 1913), русский инженер-механик флота, генерал-лейтенант.
Беляев Владимир Павлович [р.21.3(3.4).1909, Каменец-Подольский], русский советский писатель.
Брам Отто Брам (Brahm) [псевдоним; настоящая фамилия Абрахамзон (Abrahamsohn)] Отто (5.
Векторное пространство, математическое понятие, обобщающее понятие совокупности всех (свободных) векторов обычного трёхмерного пространства.
Воронихин Андрей Никифорович [17(28).10.1759, с.
Геологический разрез, геологический профиль, вертикальное сечение земной коры от её поверхности в глубину.