АЛГОРИТМИ́ЧЕСКАЯ ПРОБЛЕ́МА

АЛГОРИТМИ́ЧЕСКАЯ ПРОБЛЕ́МА, про­бле­ма, в ко­то­рой тре­бу­ет­ся най­ти еди­ный чёт­ко опи­сан­ный ме­тод (ал­го­ритм) для ре­ше­ния бес­ко­неч­ной се­рии од­но­тип­ных еди­нич­ных за­дач. Та­кие про­бле­мы на­зы­ва­ют так­же мас­со­вы­ми пробле­ма­ми. Пред­пи­са­ние для ра­бо­ты ал­го­рит­ма долж­но быть на­столь­ко чёт­ким, что­бы эту ра­бо­ту мож­но бы­ло по­ру­чить ма­ши­не. А. п. воз­ник­ли и ре­ша­лись в разл. об­лас­тях ма­те­ма­ти­ки на про­тя­же­нии всей её ис­то­рии. По­сле то­го как в 1930-х гг. в ма­те­ма­тич. ло­ги­ке бы­ло вы­ра­бо­та­но оп­ре­де­ле­ние по­ня­тия ал­го­рит­ма, поя­ви­лась воз­мож­ность до­ка­зы­вать, что не­ко­то­рые А. п. не­раз­ре­ши­мы, то есть ис­ко­мые в них ал­го­рит­мы не су­ще­ст­ву­ют, по­это­му А. п. ста­ли фор­му­ли­ро­вать как за­да­чи су­ще­ст­во­ва­ния со­от­вет­ст­вую­ще­го ал­го­рит­ма и его на­хо­ж­де­ния в слу­чае, ес­ли он су­ще­ст­ву­ет.

В тео­рии ал­го­рит­мов поч­ти од­но­вре­мен­но появилoсь не­сколь­ко раз­лич­ных по фор­ме уточ­не­ний по­ня­тия ал­го­рит­ма, ко­то­рые ока­за­лись эк­ви­ва­лент­ны­ми по су­ще­ст­ву. Ка­ж­дое из этих уточ­не­ний за­клю­ча­ет­ся в том, что вы­де­ля­ет­ся тот или иной дос­та­точ­но ши­ро­кий класс кон­крет­ных ал­го­рит­мов в фик­си­ро­ван­ном язы­ке, замк­ну­тый от­но­си­тель­но ес­те­ст­вен­ных опе­ра­ций со­еди­не­ния ал­го­рит­мов. На прак­ти­ке ма­те­ма­ти­че­ски стро­го до­ка­зы­ва­ют­ся тео­ре­мы о не­воз­мож­но­сти ре­ше­ния рас­смат­ри­вае­мой А. п. с по­мо­щью ал­го­рит­мов дан­но­го клас­са. В то же вре­мя ре­зуль­та­ты та­ко­го ро­да мож­но пе­ре­не­сти на об­ще­по­нят­ный для ма­те­ма­ти­ков язык ал­го­рит­мов, по­ни­мае­мых в ин­туи­тив­ном смыс­ле. Этот пе­ре­нос ос­но­ван на вы­ска­зан­ном А. Чёр­чем в 1936 те­зи­се (т. н. те­зи­се Чёр­ча), ко­торый ут­вер­жда­ет, что с по­мо­щью ал­горит­мов ка­ж­до­го из рас­смат­ри­вае­мых клас­сов при со­от­вет­ст­вую­щей ко­ди­ров­ке объ­ек­тов мож­но вы­пол­нить ра­бо­ту лю­бо­го ал­го­рит­ма, по­ни­мае­мо­го в ин­туи­тив­ном смыс­ле. Этот те­зис есть ес­теств.-на­уч. факт, под­кре­п­лён­ный всей ис­то­ри­ей ма­те­ма­ти­ки.

Пер­вые при­ме­ры не­раз­ре­ши­мых А. п. бы­ли об­на­ру­же­ны в са­мой тео­рии ал­го­рит­мов. К ним от­но­сит­ся про­бле­ма рас­по­зна­ва­ния са­мо­при­ме­ни­мо­сти ма­шин Тью­рин­га, про­бле­ма ос­та­нов­ки ал­го­рит­ма, про­бле­ма рас­по­зна­ва­ния при­над­леж­но­сти чис­ла дан­но­му не­ре­кур­сив­но­му мно­же­ст­ву на­ту­раль­ных чи­сел. Из не­раз­ре­ши­мых А. п. в об­лас­ти ма­те­ма­тич. ло­ги­ки сле­ду­ет от­ме­тить про­бле­му рас­по­зна­ва­ния то­ж­де­ст­вен­ной ис­тин­ности фор­мул ис­чис­ле­ния пре­ди­ка­тов 1-й сту­пе­ни (A. Чёрч, 1936) и про­бле­му рас­по­зна­ва­ния ис­тин­но­сти замк­ну­тых фор­мул в ариф­ме­ти­ке.

В сер. 20 в. бы­ла до­ка­за­на не­раз­ре­ши­мость ря­да клас­сич. А. п. в тра­диц. раз­де­лах ма­те­ма­ти­ки. Сре­ди них – ре­зуль­тат А. А. Мар­ко­ва и амер. ма­те­ма­ти­ка и ло­ги­ка Э. Л. По­ста о не­раз­ре­ши­мо­сти по­став­лен­ной А. Туэ (1914) про­бле­мы рас­по­зна­ва­ния ра­вен­ст­ва слов в по­лу­груп­пах, за­дан­ных оп­ре­де­ляю­щи­ми со­от­но­ше­ния­ми (1947), ана­ло­гич­ный ре­зуль­тат для групп (П. С. Но­ви­ков, 1955), ре­зуль­тат С. И. Адя­на (1957) об ал­го­рит­мич. не­рас­поз­на­вае­мо­сти поч­ти всех ин­ва­ри­ант­ных груп­по­вых свойств, в т. ч. свойств еди­нич­но­сти, ко­неч­но­сти, пе­рио­дич­но­сти, ре­зуль­тат Мар­ко­ва о не­раз­ре­ши­мо­сти про­бле­мы рас­по­зна­ва­ния го­мео­мор­физ­ма для 4-мер­ных мно­го­об­ра­зий (1958) и ре­зуль­тат Ю. В. Ма­тия­се­ви­ча (1971) о не­су­ще­ст­во­ва­нии ал­го­рит­ма для рас­по­зна­ва­ния раз­ре­ши­мо­сти дио­фан­то­вых урав­не­ний в це­лых чис­лах (10-я про­бле­ма Гиль­бер­та).