Подпишитесь на наши новости
Вернуться к началу с статьи up
 

НОРМА́ЛЬНЫЙ АЛГОРИ́ФМ

  • рубрика

    Рубрика: Математика

  • родственные статьи
  • image description

    В книжной версии

    Том 23. Москва, 2013, стр. 330

  • image description

    Скопировать библиографическую ссылку:




Авторы: Н. М. Нагорный

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

Вся­кий Н. а. 𝕬, яв­ля­ясь ал­го­рит­мом в не­ко­то­ром ал­фа­ви­те $A$, по­ро­ж­да­ет в нём де­тер­ми­ни­ро­ван­ный про­цесс пе­ре­ра­бот­ки слов. Ука­за­ние это­го ал­фа­ви­та вхо­дит в оп­ре­де­ле­ние Н. а. в ка­че­ст­ве со­став­ной час­ти, и про Н. а. 𝕬 го­во­рят, что он яв­ля­ет­ся Н. а. в ал­фа­ви­те $A$. Лю­бой Н. а. в фик­си­ро­ван­ном ал­фа­ви­те $A$ впол­не оп­ре­де­ля­ет­ся ука­за­ни­ем его схе­мы – упо­ря­до­чен­но­го ко­неч­но­го спи­ска фор­мул под­ста­нов­ки в $A$. Ка­ж­дая та­кая фор­му­ла пред­став­ля­ет со­бой упо­ря­до­чен­ную па­ру ($U, V$) слов в $A$. Сло­во $U$ на­зы­ва­ет­ся ле­вой ча­стью этой фор­му­лы, а $V $ её пра­вой ча­стью. Сре­ди вхо­ж­де­ний фор­мул в дан­ную схе­му не­ко­то­рые вы­де­ля­ют­ся спе­ци­аль­но и объ­яв­ля­ют­ся за­клю­чи­тель­ны­ми. Обыч­но в схе­ме Н. а. за­клю­чит. фор­му­ла за­пи­сы­ва­ет­ся в ви­де $U→·V$, а не­за­клю­чи­тель­ная – в ви­де $U→V$.

Н. а. 𝕬 в ал­фа­ви­те $A$ есть пред­пи­са­ние стро­ить, ис­хо­дя из про­из­воль­но­го сло­ва $P $ в $A$, по­сле­до­ва­тель­ность слов $P_i$ со­глас­но сле­дую­ще­му пра­ви­лу. Сло­во $P$ бе­рёт­ся в ка­че­ст­ве на­чаль­но­го сло­ва $P_0$ этой по­сле­до­ва­тель­но­сти, и про­цесс её по­строе­ния про­дол­жа­ет­ся да­лее. Пусть для не­ко­то­ро­го $i⩾0$ сло­во $P_i $ по­строе­но и про­цесс по­строе­ния рас­смат­ри­вае­мой по­сле­до­ва­тель­но­сти ещё не за­вер­шил­ся. Ес­ли в схе­ме Н. а. 𝕬 нет фор­мул, ле­вые час­ти ко­то­рых вхо­ди­ли бы в $P_i$, то $P_{i+1}$ по­ла­га­ют рав­ным $P_i$, и про­цесс по­строе­ния по­сле­до­ва­тель­но­сти на этом счи­та­ет­ся за­кон­чив­шим­ся. Ес­ли же в схе­ме 𝕬 име­ют­ся фор­му­лы с ле­вы­ми час­тя­ми, вхо­дя­щи­ми в $P_i$, то в ка­че­ст­ве $P_{i+1}$ бе­рёт­ся ре­зуль­тат под­ста­нов­ки пра­вой час­ти пер­вой из та­ких фор­мул вме­сто пер­во­го вхо­ж­де­ния её ле­вой час­ти в сло­во $P_i$, при этом про­цесс по­строе­ния по­сле­до­ва­тель­но­сти счи­та­ет­ся за­вер­шив­шим­ся, ес­ли при­ме­нён­ная на этом ша­ге фор­му­ла под­ста­нов­ки бы­ла за­клю­чи­тель­ной, и про­дол­жа­ет­ся в про­тив­ном слу­чае. Ес­ли про­цесс по­строе­ния упо­мя­ну­той по­сле­до­ва­тель­но­сти об­ры­ва­ет­ся, то го­во­рят, что рас­смат­ри­вае­мый Н. а. 𝕬 при­ме­ним к сло­ву $P$. По­след­ний член $Q$ этой по­сле­до­ва­тель­но­сти счи­та­ет­ся ре­зуль­та­том при­ме­не­ния Н. а. к сло­ву $P$ и обо­зна­ча­ет­ся сим­во­лом 𝕬($P$). При этом го­во­рят, что 𝕬 пе­ре­ра­ба­ты­ва­ет $P$ в $Q$, и пи­шут 𝕬 ($P$)=$Q$. Н. а. в ка­ком-ли­бо рас­ши­ре­нии ал­фа­ви­та $A$ на­зы­ва­ет­ся Н. а. над этим ал­фа­ви­том.

Име­ют­ся ос­но­ва­ния счи­тать, что уточ­не­ние об­ще­го пред­став­ле­ния об ал­го­рит­ме в ал­фа­ви­те, про­из­ве­дён­ное с по­мо­щью по­ня­тия Н. а., яв­ля­ет­ся аде­к­ват­ным. Имен­но, счи­та­ет­ся, что для вся­ко­го ал­го­рит­ма 𝕬 в к.-л. ал­фа­ви­те $A$ мо­жет быть по­стро­ен Н. а. 𝔅 над этим ал­фа­ви­том, пе­ре­ра­ба­ты­ваю­щий про­из­воль­ное сло­во $P$ в $A$ в тот же са­мый ре­зуль­тат, в ко­то­рый пе­ре­ра­ба­ты­ва­ет его ис­ход­ный ал­го­ритм 𝕬. Это со­гла­ше­ние из­вест­но в тео­рии ал­го­рит­мов под на­зва­ни­ем прин­ци­па нор­ма­ли­за­ции. Уточ­не­ние по­ня­тия ал­го­рит­ма, осу­ще­ст­в­лён­ное на ос­но­ве по­ня­тия Н. а., ока­зы­ва­ет­ся эк­ви­ва­лент­ным др. из­вест­ным уточ­не­ни­ям. Вслед­ст­вие это­го прин­цип нор­ма­ли­за­ции рав­но­си­лен те­зи­су Чёр­ча, пред­ла­гаю­ще­му счи­тать по­ня­тие час­тич­но ре­кур­сив­ной функ­ции аде­к­ват­ным уточ­не­ни­ем по­ня­тия вы­чис­ли­мой ариф­ме­тич. функ­ции.

Воз­ник­шие пер­во­на­чаль­но в свя­зи с ал­геб­ра­ич. про­бле­ма­ти­кой Н. а. ока­зались удоб­ным ра­бо­чим ап­па­ра­том во мно­гих ис­сле­до­ва­ни­ях, тре­бую­щих точ­но­го по­ня­тия ал­го­рит­ма, – осо­бен­но то­гда, ко­гда осн. объ­ек­ты рас­смот­ре­ния до­пус­ка­ют удоб­ное пред­став­ле­ние в ви­де слов в не­ко­то­рых ал­фа­ви­тах (та­ко­ва, напр., си­туа­ция в кон­ст­рук­тив­ной ма­те­ма­ти­ке).

Лит.: Мар­ков А. А. Тео­рия ал­го­риф­мов. М.; Л., 1954; Мар­ков А. А., На­гор­ный Н. М. Тео­рия ал­го­риф­мов. 2-е изд. М., 1996; Мен­дель­сон Э. Вве­де­ние в ма­те­ма­ти­че­скую ло­ги­ку. 4-е изд. М., 2010.

Вернуться к началу