Проблема, в к-рой требуется найти единый метод ( алгоритм).для решения бесконечной серии однотипных единичных задач. Такие проблемы иногда наз. также массовыми проблемами. А. п. возникали и решались в различных областях математики на протяжении всей ее исторпи; однако нек-рые из них долгое время не поддавались решению. Причина этого выяснилась лишь после того, как в 30-х гг. 20 в. в математнч. логике было выработано точное определение понятия алгоритма. Оказалось, что А. п. могут быть неразрешимыми, т. е. искомые в них алгоритмы могут не существовать. Таким образом, представление математиков об А. п. значительно изменилось: теперь уже новые А. п. стали формулировать как проблемы решения вопроса о существовании алгоритма для решения данной бесконечной серии однотипных задач п нахождения такого алгоритма в случае, если он существует. В алгоритмов теории почти одновременно появилось несколько различных по форме уточнений понятия алгоритма, к-рые по существу оказались эквивалентными. Каждое из этих уточнений заключается в том, что выделяется тот или иной достаточно широкий класс конкретных алгоритмов, замкнутый относительно естественных операций соединения алгоритмов. Каждое утверждение о неразрешимости той или иной А. п. представляет собой математически строго доказанную теорему о невозможности решения рассматриваемой А. п. с помощью алгоритмов данного класса. В такой форме эти теоремы можно было бы рассматривать как спецп-фич. теоремы, связанные с данным классом алгоритмов. Однако все результаты такого рода можно перенести на общепонятный для математиков язык алгоритмов, понимаемых в интуитивном смысле. Этот перенос основан на так наз. тезисе Чёрча(в зависимости от формы уточнения понятия алгоритма его наз. еще тезисом Тьюринга, или принципом нормализации), к-рый утверждает, что рассматриваемый класс алгоритмов универсален, т. е. с помощью алгоритмов этого класса по существу мо?кно выполнить работу любого алгоритма, понимаемого в интуитивном смысле. Этот тезис есть естественнонаучный факт, подкрепленный историей математики: все известные в математике алгоритмы удовлетворяют ему; все попытки построить примеры алгоритмов, выходящих за указанные рамки, не увенчались успехом. Наконец, эквивалентность различных по форме уточнений понятия алгоритма также служит подкреплением этого тезиса. Тезис Чёрча не может быть доказан, поскольку относится к математически расплывчатому понятию алгоритма в интуитивном смысле; однако он очень важен для математики, так как позволяет говорить о неразрешимости тех или иных А. и. в широком и общепонятном для математиков смысле. Первые примеры неразрешимых А. п. были обнаружены в самой теории алгоритмов. К ним относятся проблема распознавания принадлежности данному нерекурсивному множеству натуральных чисел, проблема остановки универсальной машины Тьюринга, проблема распознавания самопрцменимостн нормальных алгорифмов и др. Из А. п., выходящих за рамки самой теории алгоритмов, прежде всего следует отметить проблему распознавания тождественной истинности формул исчисления предикатов 1-й ступени, неразрешимость к-рой впервые была доказана А. Чёрчем (A. Church) в 1936. К этому результату по существу примыкают многочисленные исследования А. п. в моделей теории. Теория моделей, изучающая непустые множества с определенными на них отношениями с помощью исчисления предикатов, возникла в 30-х гг. в работах А. И. Мальцева и А. Тар-ского (A. Tarski). Им же принадлежат точные постановки многих А. п. в теории моделей и ряд фундаментальных результатов в этом направлении. Элементарной теорией данного класса Кмоделей наз. совокупность всех замкнутых формул исчисления предикатов 1-й ступени, к-рые истинны во всех моделях класса K. Класс K может состоять из одной модели. Элементарная теория Тназ. разрешимой или неразрешимой в зависимости от того, существует или нет алгоритм для распознавания но любой формуле, принадлежит она теории Тили нет. Ыек-рый обзор методов исследования А. п. в теории моделей и результатов, полученных в этом направлении, имеется в [3]. Из указанных в [3] н оставшихся пока (1977) нерешенными проблем наиболее интересен вопрос о разрешимости элементарной теории свободных групп. Многочисленные и разнообразные А. п. возникают также при конструктивном истолковании различных разделов математики. Ниже приведены основные результаты, относящиеся к А. п. в традиционных разделах математики. Долгое время оставался открытым естественный вопрос: являются ли неразрешимые А. п. специфическими для теории алгоритмов и математич. логики? Иначе говоря, существуют ли неразрешимые А. п. в традиционных разделах математики, далеких от математич. логики? Первый результат такого рода был получен в 1947 независимо друг от друга А. А. Марковым и Э. Л. Постом (Е. L. Post). Они доказали неразрешимость проблемы равенства слов (тождества) для полугрупп, к-рая была поставлена А. Туэ (А. Тhue) еще в 1914. В этой проблеме рассматриваются полугруппы, заданные с помощью конечного числа образующих (алфавита) и определяющих соотношений Элементарным преобразованием рассматриваемой полугруппы П наз. переход от слова вида к слову или обратно, где Ри Q — произвольные слова в алфавите (1). Два слова Xи У в алфавите (1) наз. эквивалентными в П, если они либо совпадают графически, либо одно из них получается из другого с помощью конечной последовательности элементарных преобразований. Множество всех классов эквивалентности с операцией умножения, к-рая определяется естественным образом через операцию приписывания слов, и есть полугруппа П, заданная образующими (1) и определяющими соотношениями (2). Проблема равенства слов (тождества) полугруппы П заключается в отыскании алгоритма для распознавания по любой паре слов X и Y полугруппы П, эквивалентны они в П или нет, т. е. тождественны определенные ими элементы полугруппы П или нет. А. А. Марков и Э. Л. Пост построили конкретные полугруппы, для к-рых уже невозможен алгоритм, решающий проблему равенства (см. [1]). Наиболее замечательный результат в этом направлении был получен П. С. Новиковым [4], [5]. Он доказал неразрешимость классич. проблемы тождества теории групп, к-рая была поставлена М. Деном (М. Dehn) в 1912 и привлекала внимание многих алгебраистов мира. Эта проблема формулируется аналогично проблеме тождества для полугрупп с тем отличием, что рассматриваются только такие системы соотношений (2), к-рые гарантируют существование в рассматриваемой полугруппе обратных элементов для всех образующих (1). П. С. Новиков доказал также неразрешимость очень важной для теории групп проблемы изоморфизма, к-рая заключалась в отыскании алгоритма для распознавания по любым двум группам, изоморфны они или нет. Позже было показано [6], что для всякой фиксированной группы Gневозможен алгоритм, к-рый проверял бы по произвольной группе, изоморфна она группе G или нет. А. А. Марков исследовал проблемы распознавания инвариантных свойств полугрупп, т. е. таких свойств, к-рые сохраняются при переходе к изоморфным полугруппам [2]. Он доказал, что если для инвариантного полугруппового свойства существует полугруппа со свойством ц другая полугруппа, не вложимая ни в какую полугруппу с этим свойством, то невозможен алгоритм для распознавания по любой полугруппе, обладает она свойством пли нет. Это по существу означает, что почти все инвариантные полугрупповые свойства алгоритмически не распознаваемы в классе полугрупп. В теории групп также был получен аналог этой фундаментальной теоремы (см. [7], [8], [9]). Из нее, в частности, вытекает следствие: пусть есть класс всех групп, обладающих инвариантным свойством ; с каждым таким классом связаны две А. п.- проблема тождества для групп из класса и проблема распознавания по любой группе, принадлежит она классу или нет. Оказывается, что для любого непустого класса по крайней мере одна из этих двух А. п. неразрешима. Аналогичная ситуация имеет место и для полугрупп. Исследовался вопрос о возможно простых заданиях групп и полугрулп с неразрешимой проблемой равенства слов. Из многочисленных исследований в этом направлении следует отметить доказательство неразрешимости проблемы равенства слов для полугруппы, заданной 7 простыми определяющими соотношениями: (см. [10]). Позже был построен пример полугруппы с 3 определяющими соотношениями и неразрешимой проблемой равенства [11]. Даже для полугрупп с одним определяющим соотношением до сих пор (1977) не найден алгоритм, решающий проблему тождества в общем случае. Такой алгоритм построен только для несократимого определяющего соотношения [12]. Для групп с одним определяющим соотношением алгоритм, решающий проблему равенства, был построен давно [13]; но уже для двух соотношений вопрос остается открытым. Минимальное число определяющих соотношений, при к-ром известны примеры групп с неразрешимой проблемой тождества, равно 12. Доказана разрешимость проблемы равенства слов для коммутативных полугрупп. Для коммутативных групп разрешима также и проблема изоморфизма. Проблема равенства слов разрешима для конечных групп, для конечно определенных простых групп, для нильпотентных групп, а также для разрешимых групп ступени 2. Но уже в классе разрешимых групп ступени 5 можно указать группу с неразрешимой проблемой равенства, заданную с помощью соответствующего тождества ступени 5 и конечного числа определяющих соотношений (см. [15]). Исследование проблемы тождества для групп с ограниченной мерой налегания определяющих слов, т. е. левых частей определяющих соотношений, было начато еще до того, как была доказана неразрешимость общей проблемы тождества. Самым сильным результатом в этом направлении в настоящее время (1977) является доказательство разрешимости проблемы тождества в классе групп, задаваемых системами определяющих соотношений, в к-рых определяющие слова могут налегать друг на друга лпшь менее чем на своей длины [14]. Если допустить налегание на длины определяющих слов, то пример группы с неразрешимой проблемой тождества строится довольно просто. Для промежутка между и вопрос остается открытым. Аналогичные исследования проводились и для полугрупп. Оказалось, что для полугрупп с максимальной мерой налегания определяющих слов, меньшей , проблема тождества разрешима, в то время как известны примеры полугрупп с неразрешимой проблемой тождества и с максимальной мерой налегания определяющих слов, равной . Из топологич. А. п. прежде всего выделяется классич. проблема распознавания гомеоморфизма для n-мерных многообразий. А. А. Марков построил пример 4-мерного многообразия , для к-рого невозможен алгоритм, распознающий по любому 4-мерному многообразию, гомеоморфно оно пли нет [17]. Известно, что при п=2 эта проблема имеет положительное решение; при n=3 вопрос остается открытым; для n-мерных многообразий при неразрешимы также проблемы распознавания комбинаторной и гомотопич. эквива-лентностей многообразий. Заметим также, что если взять полиэдр Р, фундаментальная группа к-рого имеет неразрешимую проблему тождества, то для Рневозможен алгоритм, распознающий связанную гомотопность (или свободную гомотопность) двух произвольных путей на Р, проходящих через данную точку. Получено положительное решение проблемы сопряженности в группах кос, к-рая эквивалентна топологич. проблеме распознавания эквивалентности кос [16]. Одной из наиболее знаменитых А. п. математики являлась 10-я проблема Гильберта, в к-рой требовалось найти алгоритм для распознавания по любой системе днсфантовых уравнений с целочисленными коэффициентами, имеет она целочисленное решение или нет. После появления многочисленных результатов о неразрешимых А. п. возникла гипотеза о том, что и эта проблема неразрешима. Более того, группе американских математиков удалось установить, что неразрешимость 10-й проблемы Гильберта следует из существования двуместного диофантова предиката экспоненциального роста (см. [18], [19]). Однако построить такой предикат им не удалось. Они доказали лишь неразрешимость проблемы распознавания существования целочисленных решений показательных уравнений. Искомый диофантов предикат экспоненциального роста впервые был построен в 1970 (см. [20], [21] ). Тем самым впервые была доказана неразрешимость 10-й проблемы Гильберта. В теории алгоритмов доказано существование неразрешимых А. п. различных неразрешимости степеней. Многочисленные исследования возникающих в математике А. п. показали, что каждая из этих А. п. в общем случае имеет максимальную степень неразрешимости, а в своих частных вариантах (например, проблема тождества в конкретных полугруппах или группах) может иметь любую наперед заданную степень неразрешимости. Лит.:[1] Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; [2] Марков А. А., "Тр. Матем. ин-та АН СССР", 1954, т. 42, с. 1-376; [3] Ершов Ю. Л. и др., "Успехи матем. наук", 1965, т. 20, № 4, с. 37-108; [4] Новиков П. С., "Докл. АН СССР", 1952, т. 85, № 4, с. 709 — 12; [5] Новиков П. С., "Тр. Матем. нн-та АН СССР", 1955, т. 44, с. 1-444; [6] Адян С. И., "Тр. Моск. матем. об-ва", 1957, т. 6, с. 231-98; [7] Адян С. И., "Докл. АН СССР", 1957. т. 117, Л5 1, с. 9 — 12; [8] А д я н С. И., "Докл. АН СССР", 1958. т. 123, Л" 1, с. 13-16; [9] Rabin M. О., "Ann. math.", 1958, v. 67, № 1, p. 172-94; [10] Цейтин Г. С., "Тр. Матем. ин-та АН СССР", 1958, т. 52, с. 172-89; [11] Матиясевич Ю. В., "Докл. АН СССР", 1967, т. 173, № 6, с. 1264-6; [12] Адян С. И., "Тр. Матем. ин-та АН СССР", 1966, т. 85, с. 1 — 123; [13] Магнус В., "Успехи матем. наук", 1941, Bd 8, с. 365-76; [14] Lуndоn R. С., "Math. Ann.", 1966, Bd. 166, № 3, S. 208-28; [15] Ремесленников В. Н., "Алгебра и логика", 1973, т. 12, № 5, с. 577-602; [16] Гарсаид Ф. А., "Математика", 1970, т. 14, № 4, с. 113-32; [17] Марков А. А., "Докл. АН СССР", 1958, т. 123, № 6, с. 978-80; [18] Дэвис М., Путнам X., РобинсонД ж., "Математика", 1964, т. 8, № 5, с. 69-79; [19] Робинсон Д ж., "Математика", 1964, т. 8, М!> 5, с. 3-14; [20] Матиясевич Ю. В., "Докл. АН СССР", 1970, т. 191, М 2, с. 279 — 82; [21] Матиясевич Ю. В., "Изв. АН СССР. Сер. матем.", 1971, т. 35, Mb 1, с. 3-30. С.
Источник: Математическая энциклопедия на Gufo.megufo.me
проблема, в к-рой требуется найти единый метод ( алгоритм).для решения бесконечной серии однотипных единичных задач. Такие проблемы иногда наз. также массовыми проблемами. А. п. возникали и решались в различных областях математики на протяжении всей ее исторпи; однако нек-рые из них долгое время не поддавались решению. Причина этого выяснилась лишь после того, как в 30-х гг. 20 в. в математнч. логике было выработано точное определение понятия алгоритма. Оказалось, что А. п. могут быть неразрешимыми, т. е. искомые в них алгоритмы могут не существовать. Таким образом, представление математиков об А. п. значительно изменилось: теперь уже новые А. п. стали формулировать как проблемы решения вопроса о существовании алгоритма для решения данной бесконечной серии однотипных задач п нахождения такого алгоритма в случае, если он существует.
В алгоритмов теории почти одновременно появилось несколько различных по форме уточнений понятия алгоритма, к-рые по существу оказались эквивалентными. Каждое из этих уточнений заключается в том, что выделяется тот или иной достаточно широкий класс конкретных алгоритмов, замкнутый относительно естественных операций соединения алгоритмов. Каждое утверждение о неразрешимости той или иной А. п. представляет собой математически строго доказанную теорему о невозможности решения рассматриваемой А. п. с помощью алгоритмов данного класса. В такой форме эти теоремы можно было бы рассматривать как спецп-фич. теоремы, связанные с данным классом алгоритмов. Однако все результаты такого рода можно перенести на общепонятный для математиков язык алгоритмов, понимаемых в интуитивном смысле. Этот перенос основан на так наз. тезисе Чёрча(в зависимости от формы уточнения понятия алгоритма его наз. еще тезисом Тьюринга, или принципом нормализации), к-рый утверждает, что рассматриваемый класс алгоритмов универсален, т. е. с помощью алгоритмов этого класса по существу мо?кно выполнить работу любого алгоритма, понимаемого в интуитивном смысле. Этот тезис есть естественнонаучный факт, подкрепленный историей математики: все известные в математике алгоритмы удовлетворяют ему; все попытки построить примеры алгоритмов, выходящих за указанные рамки, не увенчались успехом. Наконец, эквивалентность различных по форме уточнений понятия алгоритма также служит подкреплением этого тезиса. Тезис Чёрча не может быть доказан, поскольку относится к математически расплывчатому понятию алгоритма в интуитивном смысле; однако он очень важен для математики, так как позволяет говорить о неразрешимости тех или иных А. и. в широком и общепонятном для математиков смысле.
Первые примеры неразрешимых А. п. были обнаружены в самой теории алгоритмов. К ним относятся проблема распознавания принадлежности данному нерекурсивному множеству натуральных чисел, проблема остановки универсальной машины Тьюринга, проблема распознавания самопрцменимостн нормальных алгорифмов и др.
Из А. п., выходящих за рамки самой теории алгоритмов, прежде всего следует отметить проблему распознавания тождественной истинности формул исчисления предикатов 1-й ступени, неразрешимость к-рой впервые была доказана А. Чёрчем (A. Church) в 1936. К этому результату по существу примыкают многочисленные исследования А. п. в моделей теории. Теория моделей, изучающая непустые множества с определенными на них отношениями с помощью исчисления предикатов, возникла в 30-х гг. в работах А. И. Мальцева и А. Тар-ского (A. Tarski). Им же принадлежат точные постановки многих А. п. в теории моделей и ряд фундаментальных результатов в этом направлении. Элементарной теорией данного класса Кмоделей наз. совокупность всех замкнутых формул исчисления предикатов 1-й ступени, к-рые истинны во всех моделях класса K. Класс K может состоять из одной модели. Элементарная теория Тназ. разрешимой или неразрешимой в зависимости от того, существует или нет алгоритм для распознавания но любой формуле, принадлежит она теории Тили нет. Ыек-рый обзор методов исследования А. п. в теории моделей и результатов, полученных в этом направлении, имеется в [3]. Из указанных в [3] н оставшихся пока (1977) нерешенными проблем наиболее интересен вопрос о разрешимости элементарной теории свободных групп.
Многочисленные и разнообразные А. п. возникают также при конструктивном истолковании различных разделов математики. Ниже приведены основные результаты, относящиеся к А. п. в традиционных разделах математики.
Долгое время оставался открытым естественный вопрос: являются ли неразрешимые А. п. специфическими для теории алгоритмов и математич. логики? Иначе говоря, существуют ли неразрешимые А. п. в традиционных разделах математики, далеких от математич. логики? Первый результат такого рода был получен в 1947 независимо друг от друга А. А. Марковым и Э. Л. Постом (Е. L. Post). Они доказали неразрешимость проблемы равенства слов (тождества) для полугрупп, к-рая была поставлена А. Туэ (А. Тhue) еще в 1914. В этой проблеме рассматриваются полугруппы, заданные с помощью конечного числа образующих (алфавита)
и определяющих соотношений
Элементарным преобразованием рассматриваемой полугруппы П наз. переход от слова вида 
к слову 
или обратно, где Ри Q - произвольные слова в алфавите (1). Два слова Xи У в алфавите (1) наз. эквивалентными в П, если они либо совпадают графически, либо одно из них получается из другого с помощью конечной последовательности элементарных преобразований. Множество всех классов эквивалентности с операцией умножения, к-рая определяется естественным образом через операцию приписывания слов, и есть полугруппа П, заданная образующими (1) и определяющими соотношениями (2). Проблема равенства слов (тождества) полугруппы П заключается в отыскании алгоритма для распознавания по любой паре слов X и Y полугруппы П, эквивалентны они в П или нет, т. е. тождественны определенные ими элементы полугруппы П или нет. А. А. Марков и Э. Л. Пост построили конкретные полугруппы, для к-рых уже невозможен алгоритм, решающий проблему равенства (см. [1]).
Наиболее замечательный результат в этом направлении был получен П. С. Новиковым [4], [5]. Он доказал неразрешимость классич. проблемы тождества теории групп, к-рая была поставлена М. Деном (М. Dehn) в 1912 и привлекала внимание многих алгебраистов мира. Эта проблема формулируется аналогично проблеме тождества для полугрупп с тем отличием, что рассматриваются только такие системы соотношений (2), к-рые гарантируют существование в рассматриваемой полугруппе обратных элементов для всех образующих (1). П. С. Новиков доказал также неразрешимость очень важной для теории групп проблемы изоморфизма, к-рая заключалась в отыскании алгоритма для распознавания по любым двум группам, изоморфны они или нет. Позже было показано [6], что для всякой фиксированной группы Gневозможен алгоритм, к-рый проверял бы по произвольной группе, изоморфна она группе G или нет.
А. А. Марков исследовал проблемы распознавания инвариантных свойств полугрупп, т. е. таких свойств, к-рые сохраняются при переходе к изоморфным полугруппам [2]. Он доказал, что если для инвариантного полугруппового свойства 
существует полугруппа со свойством 
ц другая полугруппа, не вложимая ни в какую полугруппу с этим свойством, то невозможен алгоритм для распознавания по любой полугруппе, обладает она свойством 
пли нет. Это по существу означает, что почти все инвариантные полугрупповые свойства алгоритмически не распознаваемы в классе полугрупп. В теории групп также был получен аналог этой фундаментальной теоремы (см. [7], [8], [9]). Из нее, в частности, вытекает следствие: пусть 
есть класс всех групп, обладающих инвариантным свойством 
; с каждым таким классом связаны две А. п.- проблема тождества для групп из класса 
и проблема распознавания по любой группе, принадлежит она классу 
или нет. Оказывается, что для любого непустого класса 
по крайней мере одна из этих двух А. п. неразрешима. Аналогичная ситуация имеет место и для полугрупп.
Исследовался вопрос о возможно простых заданиях групп и полугрулп с неразрешимой проблемой равенства слов. Из многочисленных исследований в этом направлении следует отметить доказательство неразрешимости проблемы равенства слов для полугруппы, заданной 7 простыми определяющими соотношениями:
(см. [10]). Позже был построен пример полугруппы с 3 определяющими соотношениями и неразрешимой проблемой равенства [11]. Даже для полугрупп с одним определяющим соотношением до сих пор (1977) не найден алгоритм, решающий проблему тождества в общем случае. Такой алгоритм построен только для несократимого определяющего соотношения [12]. Для групп с одним определяющим соотношением алгоритм, решающий проблему равенства, был построен давно [13]; но уже для двух соотношений вопрос остается открытым. Минимальное число определяющих соотношений, при к-ром известны примеры групп с неразрешимой проблемой тождества, равно 12. Доказана разрешимость проблемы равенства слов для коммутативных полугрупп. Для коммутативных групп разрешима также и проблема изоморфизма. Проблема равенства слов разрешима для конечных групп, для конечно определенных простых групп, для нильпотентных групп, а также для разрешимых групп ступени 2. Но уже в классе разрешимых групп ступени 5 можно указать группу с неразрешимой проблемой равенства, заданную с помощью соответствующего тождества ступени 5 и конечного числа определяющих соотношений (см. [15]).
Исследование проблемы тождества для групп с ограниченной мерой налегания определяющих слов, т. е. левых частей определяющих соотношений, было начато еще до того, как была доказана неразрешимость общей проблемы тождества. Самым сильным результатом в этом направлении в настоящее время (1977) является доказательство разрешимости проблемы тождества в классе групп, задаваемых системами определяющих соотношений, в к-рых определяющие слова могут налегать друг на друга лпшь менее чем на 
своей длины [14]. Если допустить налегание на 
длины определяющих слов, то пример группы с неразрешимой проблемой тождества строится довольно просто. Для промежутка между 
и 
вопрос остается открытым. Аналогичные исследования проводились и для полугрупп. Оказалось, что для полугрупп с максимальной мерой налегания определяющих слов, меньшей 
, проблема тождества разрешима, в то время как известны примеры полугрупп с неразрешимой проблемой тождества и с максимальной мерой налегания определяющих слов, равной 
.
Из топологич. А. п. прежде всего выделяется классич. проблема распознавания гомеоморфизма для n-мерных многообразий. А. А. Марков построил пример 4-мерного многообразия 
, для к-рого невозможен алгоритм, распознающий по любому 4-мерному многообразию, гомеоморфно оно 
пли нет [17]. Известно, что при п=2 эта проблема имеет положительное решение; при n=3 вопрос остается открытым; для n-мерных многообразий при 
неразрешимы также проблемы распознавания комбинаторной и гомотопич. эквива-лентностей многообразий. Заметим также, что если взять полиэдр Р, фундаментальная группа к-рого имеет неразрешимую проблему тождества, то для Рневозможен алгоритм, распознающий связанную гомотопность (или свободную гомотопность) двух произвольных путей на Р, проходящих через данную точку. Получено положительное решение проблемы сопряженности в группах кос, к-рая эквивалентна топологич. проблеме распознавания эквивалентности кос [16].
Одной из наиболее знаменитых А. п. математики являлась 10-я проблема Гильберта, в к-рой требовалось найти алгоритм для распознавания по любой системе днсфантовых уравнений с целочисленными коэффициентами, имеет она целочисленное решение или нет. После появления многочисленных результатов о неразрешимых А. п. возникла гипотеза о том, что и эта проблема неразрешима. Более того, группе американских математиков удалось установить, что неразрешимость 10-й проблемы Гильберта следует из существования двуместного диофантова предиката экспоненциального роста (см. [18], [19]). Однако построить такой предикат им не удалось. Они доказали лишь неразрешимость проблемы распознавания существования целочисленных решений показательных уравнений. Искомый диофантов предикат экспоненциального роста впервые был построен в 1970 (см. [20], [21] ). Тем самым впервые была доказана неразрешимость 10-й проблемы Гильберта.
В теории алгоритмов доказано существование неразрешимых А. п. различных неразрешимости степеней. Многочисленные исследования возникающих в математике А. п. показали, что каждая из этих А. п. в общем случае имеет максимальную степень неразрешимости, а в своих частных вариантах (например, проблема тождества в конкретных полугруппах или группах) может иметь любую наперед заданную степень неразрешимости.
Лит.:[1] Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965; [2] Марков А. А., "Тр. Матем. ин-та АН СССР", 1954, т. 42, с. 1-376; [3] Ершов Ю. Л. и др., "Успехи матем. наук", 1965, т. 20, № 4, с. 37-108; [4] Новиков П. С., "Докл. АН СССР", 1952, т. 85, № 4, с. 709 - 12; [5] Новиков П. С., "Тр. Матем. нн-та АН СССР", 1955, т. 44, с. 1-444; [6] Адян С. И., "Тр. Моск. матем. об-ва", 1957, т. 6, с. 231-98; [7] Адян С. И., "Докл. АН СССР", 1957. т. 117, Л5 1, с. 9 - 12; [8] А д я н С. И., "Докл. АН СССР", 1958. т. 123, Л" 1, с. 13-16; [9] Rabin M. О., "Ann. math.", 1958, v. 67, № 1, p. 172-94; [10] Цейтин Г. С., "Тр. Матем. ин-та АН СССР", 1958, т. 52, с. 172-89; [11] Матиясевич Ю. В., "Докл. АН СССР", 1967, т. 173, № 6, с. 1264-6; [12] Адян С. И., "Тр. Матем. ин-та АН СССР", 1966, т. 85, с. 1 - 123; [13] Магнус В., "Успехи матем. наук", 1941, Bd 8, с. 365-76; [14] Lуndоn R. С., "Math. Ann.", 1966, Bd. 166, № 3, S. 208-28; [15] Ремесленников В. Н., "Алгебра и логика", 1973, т. 12, № 5, с. 577-602; [16] Гарсаид Ф. А., "Математика", 1970, т. 14, № 4, с. 113-32; [17] Марков А. А., "Докл. АН СССР", 1958, т. 123, № 6, с. 978-80; [18] Дэвис М., Путнам X., РобинсонД ж., "Математика", 1964, т. 8, № 5, с. 69-79; [19] Робинсон Д ж., "Математика", 1964, т. 8, М!> 5, с. 3-14; [20] Матиясевич Ю. В., "Докл. АН СССР", 1970, т. 191, М 2, с. 279 - 82; [21] Матиясевич Ю. В., "Изв. АН СССР. Сер. матем.", 1971, т. 35, Mb 1, с. 3-30. С.
Математическая энциклопедия. — М.: Советская энциклопедия. И. М. Виноградов. 1977—1985.
dic.academic.ru
В предыдущей главе обсуждалась сложность решения задач. Решением частной задачи является найденный объект: число, вектор, матрица, граф, маршрут в конкретной сети. Сложность решения такой задачи – это некоторое натуральное число – количество элементарных шагов.
Решением общей задачи является алгоритм, с помощью которого может быть решена любая частная задача, получаемая из данной общей задачи. Сложность общей задачи – это функция, аргументом которой является сложность исходных данных. Это сложность наилучшего алгоритма (из многих существующих и потенциально возможных), решающего задачу. В тени оставался вопрос о том, существует ли хотя бы один алгоритм, решающий эту общую задачу.
Рассмотрим в качестве примера задачу о диофантовых уравнениях.
Диофантовы уравнения (названы в память греческого математика Диофанта, жившего в III в. н. э.) имеют вид
P(x1, x2, ..., xn) = Q(x1, x2, ..., xn),
где Р и Q – полиномы, например:
ax2 + bx + c = y2; axn + bxn = czn; ax3 + bx2y + cxy2 + dy3 = 1.
Коэффициенты a, b, c и степень n – целые числа; решения – значения x, y, z – также должны быть целыми числами. Конечно, решения не всегда существуют: вспомним хотя бы известную теорему Ферма о том, что уравнение xn + yn = zn, n > 2, не имеет целочисленных решений. Теорема была сформулирована Пьером де Ферма в середине XVII в. без доказательства и доказана Эндрю Уайлсом в 1995 г.
Математик Давид Гильберт сформулировал задачу (известную как 10-я проблема Гильберта): указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых числах. Иначе говоря, разработать алгоритм, на вход которого подается запись конкретного уравнения (текст), а на выходе появляется по окончании работы одно из двух текстовых значений: «решение существует», «решение не существует».
Эта задача распознавания проще, чем задача нахождения решения, т.е. определения числовых значений x, y, z, …, удовлетворяющих диофантову уравнению. Но все равно она достаточно амбициозна, если учесть тот срок, который потребовался математикам для ответа на такой же вопрос, сформулированный в теореме Ферма.
Неудивительно, что на решение 10-й проблемы Гильберта ушло 70 лет, и ответ был неожиданным: Ю.Матиясевич доказал, что такого алгоритма не существует!
Общая задача определяется:
1) списком параметров lp – свободных переменных, конкретные значения которых не определены;
2) формулировкой условий – свойств, которыми должен обладать ответ (решение задачи).
Решением такой задачи z(lp) со списком параметров lp является алгоритм (lp) – тоже кодируемый строкой символов, интерпретируемой (выполняемой) некоторым вычислителем, причем важно то, что некоторые участки строки интерпретируются многократно (циклически) потенциально неограниченное число раз. Более точно можно сказать, что решением массовой задачи являются алгоритм + вычислитель.
Частная задача получается из общей задачи, если всем параметрам общей задачи придать конкретные значения (задать исходные данные).
Некоторые массовые задачи решения не имеют. Это значит, что не существует алгоритма как решения массовой задачи z(lp). Если же для каждого параметра задачи из списка lp задать конкретное значение из предметной области, т.е. превратить массовую задачу в индивидуальную, то решение вполне может найтись. Различие состоит в том, что для разных частных задач z1 , z2, z3 ,…, полученных из одной общей задачи z, могут потребоваться разные алгоритмы 1 , 2 , 3 ,…. Поэтому более точно: не существует общего алгоритма, решающего массовую задачу. Возможно, что только для некоторых параметров задаются конкретные значения, т.е. список lp уменьшается до более короткого списка lp‘, но при этом «упрощенная» общая задача получает решение.
В связи с этой проблемой возникли задачи о задачах Z(z(lp)). Задача Z о задаче z(lp) может быть сформулирована так: существует ли алгоритм (lp), решающий задачу z(lp)?
Для того чтобы такие задачи можно было решать на строго научной основе, математическими методами, должно быть введено строгое понятие алгоритма. Формулировок таких понятий в теории алгоритмов было введено несколько. Наиболее известными являются машина Тьюринга, машина Поста, алгорифмы Маркова. Было доказано, что они эквивалентны в том смысле, что алгоритм, представленный в одной форме, может быть переведен в другую.
studfiles.net
