Cтраница 2
Начиная с примера Черча 1936 и по 1944 все доказательства неразрешимости массовых проблем проводились или могли быть проведены след, единообразным методом. Возник вопрос, для всякой ли неразрешимой проблемы разрешения ее неразрешимость может быть установлена таким способом. Проблема сводимости стояла в центре исследований по теории А. Был построен пример неразрешимой проблемы разрешения ( для перечислимого множества), неразрешимость к-рой нельзя доказать сведением к этой проблеме проблемы Черча. Мучник показал даже больше, а именно, что не только проблема Черча, но и никакая другая проблема не может служить стандартной неразрешимой проблемой в том смысле, что доказательство неразрешимости любой неразрешимой проблемы разрешения для перечислимого множества могло бы быть сведено к доказательству неразрешимости этой стандартной проблемы. [16]
Тьюринга машина 5 - 265 Тьюринга тезис 5 - 265 - см. также Массовая проблема Тэйлор О. [17]
Ду синтаксическим и семантическим ( а потом и прагматическим) аспектами науки; получены важнейшие результаты, свидетельствующие о неполноте формализованных систем, включающих в себя арифметику натуральных чисел, а также о невозможности доказательства непротиворечивости таких систем средствами, формализуемыми в этих же системах; доказано существование областей науки, в которых имеются алгоритмически неразрешимые массовые проблемы; показана невозможность формализации понятия истины в некоторой теории средствами этой же теории и др. Эти результаты, как мы уже говорили в § 6 этой главы, свидетельствуют о том, что процесс математизации науки, переплетение в ней точных и эмпирически-описательных методов тем не менее сохраняет в целом ее двухэтажный характер. На шервом этаже знания, наиболее близком к его фундаменту - практике - располагается содержательная, неформализованная часть знания, над которой надстраивается этаж математических, математизированных, логически систематизированных, наконец, формальных теорий. [18]
В частности: аппараты теории алгорифмов и обще ( теории исчислений доведены до высокого уровня тех нической оснащенности, обстоятельно исследовань связи между различными вариантами этих аппаратов огромную роль в разъяснении ряда коренных вопросов оснований математики сыграл созданный К - Геделеы конструктивный метод арифметизации формально-дедуктивных систем и арифметической интерпретации поня тия выводимости; широкую известность получили теО ремы о невозможности алгорифмов, решающих некоторые ( длительное время привлекавшие внимание математиков массовые проблемы теории логических и логико-математических исчислений, алгебры, топологии математического анализа и других разделов математики; значительные результаты достигнуты в изучении различных способов сведения одних массовых проблем к другим и в исследовании иерархии сложностей массовых проблем; введение в обиход математики разнообразных критериев сложности конструктивных объектов ( например, алгорифмов) и конструктивных процессов ( например, процессов применения алгорифмов к исходным данным привело к формированию новых многообещающих направлений исследований, уже зарекомендовавших себя серьезными результатами; шаг за шагом уточнялись и углублялись принципы конструктивного понимания математических суждений о конструктивных объектах; были разработаны и получили значительное развитие аппараты логического вывода, согласованные с конструктивным пониманием математических суждений. [19]
В частности: аппараты теории алгорифмов и обще ( теории исчислений доведены до высокого уровня тех нической оснащенности, обстоятельно исследовань связи между различными вариантами этих аппаратов огромную роль в разъяснении ряда коренных вопросов оснований математики сыграл созданный К - Геделеы конструктивный метод арифметизации формально-дедуктивных систем и арифметической интерпретации поня тия выводимости; широкую известность получили теО ремы о невозможности алгорифмов, решающих некоторые ( длительное время привлекавшие внимание математиков массовые проблемы теории логических и логико-математических исчислений, алгебры, топологии математического анализа и других разделов математики; значительные результаты достигнуты в изучении различных способов сведения одних массовых проблем к другим и в исследовании иерархии сложностей массовых проблем; введение в обиход математики разнообразных критериев сложности конструктивных объектов ( например, алгорифмов) и конструктивных процессов ( например, процессов применения алгорифмов к исходным данным привело к формированию новых многообещающих направлений исследований, уже зарекомендовавших себя серьезными результатами; шаг за шагом уточнялись и углублялись принципы конструктивного понимания математических суждений о конструктивных объектах; были разработаны и получили значительное развитие аппараты логического вывода, согласованные с конструктивным пониманием математических суждений. [20]
В частности: аппараты теории алгорифмов и обще ( теории исчислений доведены до высокого уровня тех нической оснащенности, обстоятельно исследовань связи между различными вариантами этих аппаратов огромную роль в разъяснении ряда коренных вопросов оснований математики сыграл созданный К - Геделеы конструктивный метод арифметизации формально-дедуктивных систем и арифметической интерпретации поня тия выводимости; широкую известность получили теО ремы о невозможности алгорифмов, решающих некоторые ( длительное время привлекавшие внимание математиков массовые проблемы теории логических и логико-математических исчислений, алгебры, топологии математического анализа и других разделов математики; значительные результаты достигнуты в изучении различных способов сведения одних массовых проблем к другим и в исследовании иерархии сложностей массовых проблем; введение в обиход математики разнообразных критериев сложности конструктивных объектов ( например, алгорифмов) и конструктивных процессов ( например, процессов применения алгорифмов к исходным данным привело к формированию новых многообещающих направлений исследований, уже зарекомендовавших себя серьезными результатами; шаг за шагом уточнялись и углублялись принципы конструктивного понимания математических суждений о конструктивных объектах; были разработаны и получили значительное развитие аппараты логического вывода, согласованные с конструктивным пониманием математических суждений. [21]
Примером может служить 10-я проблема Гильберта, состоящая в построении алгоритма, к-рый позволил бы для любого заданного многочлена с целыми коэффициентами узнать, существуют ли целые значения переменных, обращающие этот многочлен в нуль. Многие массовые проблемы долгое время не поддавались решению; впоследствии оказалось, что трудность их решения имеет принципиальный характер. [22]
Пусть в машине Тьюринга зафиксирована какая-нибудь конфигурация. Возникает следующая массовая проблема. [23]
Если дана некоторая библиотека ( произвольная; в этом массовость проблемы), для разделов которой составлены каталоги, то проблема составления каталога всех несамоназывающихся и только несамоназывающихся каталогов ( см. гл. Рассмотрим некоторые примеры подобных абсурдных массовых проблем. [24]
Согласно общему принципу ( тезис Черча), интуитивная вычислимость эквивалентна частичной рекурсивно-сти функции. Отсюда вытекает, что соответствующая массовая проблема для семейства / алгоритмически разрешима, если н только если характеристическая функция Е вычислима. [25]
Одним из свойств алгоритма является его массовость. Это означает, что алгоритм представляет собой способ решения некоторой массовой проблемы, формулируемой в виде проблемы отображения не одного, а целого множества входных слов в соответствующие им выходные слова. [26]
В настоящее время ( к 1978) установлена неразрешимость большого числа естественных массовых проблем анализа. [27]
Неразрешимость проблемы распознавания применимости нормального алгоритма к слову в А означает отсутствие общего метода, который для любого алгоритма и любого слова в А мог бы дать интересующий нас ответ. Ограничивая класс алгоритмов или класс обследуемых слов, или и то и другое, можно в некоторых случаях получить разрешимые массовые проблемы. [28]
Следующее важное наблюдение в этой области состоит в том, что различные NP-проблемы можно сводить одну к другой. Под этим мы подразумеваем ( несколько расплывчато) следующее: существует полиномиальный алгоритм, который конструирует для каждой индивидуальной задачи ( или, короче ИЗ) массовой проблемы А некоторую ИЗ массовой проблемы В таким образом, что ответ на эту ИЗ проблемы А будет да в том и только том случае, когда таков же ответ на соответствующую ИЗ проблемы В. Есть несколько способов уточнить это понятие, но суть дела от этого не изменится - такое преобразование ( сведение, редукция) действительно сводит решение проблемы А к решению проблемы В. Эти преобразования используются очень часто и мы уже доказали таким способом несколько теорем в этой книге. Например, мы сводили двудольную задачу об / - факторе к задаче о потоке в разд. Очевидно, что если проблему А можно свести к проблеме В, то проблема В не может быть существенно проще, чем проблема А. Например, если существует полиномиальный алгоритм для решения проблемы В, то должен также существовать полиномиальный алгоритм, решающий проблему А. [29]
Следующее важное наблюдение в этой области состоит в том, что различные NP-проблемы можно сводить одну к другой. Под этим мы подразумеваем ( несколько расплывчато) следующее: существует полиномиальный алгоритм, который конструирует для каждой индивидуальной задачи ( или, короче ИЗ) массовой проблемы А некоторую ИЗ массовой проблемы В таким образом, что ответ на эту ИЗ проблемы А будет да в том и только том случае, когда таков же ответ на соответствующую ИЗ проблемы В. Есть несколько способов уточнить это понятие, но суть дела от этого не изменится - такое преобразование ( сведение, редукция) действительно сводит решение проблемы А к решению проблемы В. Эти преобразования используются очень часто и мы уже доказали таким способом несколько теорем в этой книге. Например, мы сводили двудольную задачу об / - факторе к задаче о потоке в разд. Очевидно, что если проблему А можно свести к проблеме В, то проблема В не может быть существенно проще, чем проблема А. Например, если существует полиномиальный алгоритм для решения проблемы В, то должен также существовать полиномиальный алгоритм, решающий проблему А. [30]