Большая техническая энциклопедия
2 4 7
D L N
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Э Ю Я
МА МГ МЕ МИ МЛ МН МО МУ МЫ МЯ

Массовая проблема

 
Простейшая массовая проблема, посильная даже для любого ребенка ( приведена ниже), оказывается неразрешимой проблемой. Если же применить к ней волшебное свойство человека совершать неконструктивные действия, то после этого уже не нужен никакой алгоритм.
Хотя массовая проблема перечисления всех экстремальных унтер-решений систем уравнений в словах алгоритмически неразрешима, для многих конкретных систем и даже для больших классов она может быть решена.
Алгоритм, Массовая проблема, Разрешимое и перечислимое множества, Сводимость), исчисление Х - конверсин ( см. Оператор абстракции, Функция), логика комбинаторная и др. Из общих науч. Успехи, достигнутые в формальной теории дедукции, способствовали применению точных методов в разработке широкого комплекса проблем теории индукции и индуктивной логики ( см. ст. Логика индуктивная, раздел Современная логика индуктивная, ст. Научная индукция, Неполная индукция, Популярная индукция), и вероятностной логики.
Степени трудности массовых проблем, Докл.
Частным случаем массовых проблем являются разрешения проблемы.
Степени трудности массовых проблем, Докл.
Обратно, всякая массовая проблема, соответств. Отсюда ясна важная роль проблем разрешения. Среди проблем разрешения выделяются проблемы, поставленные для классов доказуемых формул исчислении.
Такие проблемы называют также массовыми проблемами. Предписание для работы алгоритма должно быть настолько четким, чтобы эту работу можно было поручить машине.
Читатель видит, что некоторые массовые проблемы, вовсе не имеющие абсурдного характера, неразрешимы потому, что из их разрешимости можно было бы вывести абсурд. Нужно заметить, что неразрешимость ( массовой) проблемы распознавания применимости нормального алгоритма в Л к слову в А совсем не означает, что мы вообще не можем распознавать применимость конкретного алгоритма к конкретному слову или к различным словам. Например, нормальный алгоритм - применим к любому слову в Л, и это сразу видно. Любой алгоритм c - v - o, где а - буква Л, тоже применим к любому слову в А.
Всякий алгоритм представляет собой способ решения некоторой массовой проблемы, формулируемой в виде проблемы переработки не одного, а целого множества входных слов в соответствующие им выходные слова. Поскольку как условие, так и решение любой задачи может быть выражено в виде отдельных слов, всякий алгоритм можно рассматривать как некоторое универсальное средство для решения целого класса задач.
Приведены также основные принципы доказательств алгоритмической неразрешимости некоторых простейших массовых проблем.
Понятие задачи в общем виде уточняется при помощи понятия массовой проблемы, к-рая состоит в требовании найти единый А.
Понятие задачи в общем виде уточняется при помощи понятия массовой проблемы.
Из теоремы о неполноте но существу вытекает и существование неразрешимых массовых проблем, а именно: неразрешимой является семантнч.
На основании доказанной теоремы удается установить алгоритмическую неразрешимость и некоторых других массовых проблем, возникающих в теории машин Тьюринга. При этом широко применяется метод сводимости, заключающийся в следующем.

Начиная с примера Черча 1936 и по 1944 все доказательства неразрешимости массовых проблем проводились или могли быть проведены след, единообразным методом. Возник вопрос, для всякой ли неразрешимой проблемы разрешения ее неразрешимость может быть установлена таким способом. Проблема сводимости стояла в центре исследований по теории А. Был построен пример неразрешимой проблемы разрешения ( для перечислимого множества), неразрешимость к-рой нельзя доказать сведением к этой проблеме проблемы Черча. Мучник показал даже больше, а именно, что не только проблема Черча, но и никакая другая проблема не может служить стандартной неразрешимой проблемой в том смысле, что доказательство неразрешимости любой неразрешимой проблемы разрешения для перечислимого множества могло бы быть сведено к доказательству неразрешимости этой стандартной проблемы.
Тьюринга машина 5 - 265 Тьюринга тезис 5 - 265 - см. также Массовая проблема Тэйлор О.
Ду синтаксическим и семантическим ( а потом и прагматическим) аспектами науки; получены важнейшие результаты, свидетельствующие о неполноте формализованных систем, включающих в себя арифметику натуральных чисел, а также о невозможности доказательства непротиворечивости таких систем средствами, формализуемыми в этих же системах; доказано существование областей науки, в которых имеются алгоритмически неразрешимые массовые проблемы; показана невозможность формализации понятия истины в некоторой теории средствами этой же теории и др. Эти результаты, как мы уже говорили в § 6 этой главы, свидетельствуют о том, что процесс математизации науки, переплетение в ней точных и эмпирически-описательных методов тем не менее сохраняет в целом ее двухэтажный характер. На шервом этаже знания, наиболее близком к его фундаменту - практике - располагается содержательная, неформализованная часть знания, над которой надстраивается этаж математических, математизированных, логически систематизированных, наконец, формальных теорий.
В частности: аппараты теории алгорифмов и обще ( теории исчислений доведены до высокого уровня тех нической оснащенности, обстоятельно исследовань связи между различными вариантами этих аппаратов огромную роль в разъяснении ряда коренных вопросов оснований математики сыграл созданный К - Геделеы конструктивный метод арифметизации формально-дедуктивных систем и арифметической интерпретации поня тия выводимости; широкую известность получили теО ремы о невозможности алгорифмов, решающих некоторые ( длительное время привлекавшие внимание математиков массовые проблемы теории логических и логико-математических исчислений, алгебры, топологии математического анализа и других разделов математики; значительные результаты достигнуты в изучении различных способов сведения одних массовых проблем к другим и в исследовании иерархии сложностей массовых проблем; введение в обиход математики разнообразных критериев сложности конструктивных объектов ( например, алгорифмов) и конструктивных процессов ( например, процессов применения алгорифмов к исходным данным привело к формированию новых многообещающих направлений исследований, уже зарекомендовавших себя серьезными результатами; шаг за шагом уточнялись и углублялись принципы конструктивного понимания математических суждений о конструктивных объектах; были разработаны и получили значительное развитие аппараты логического вывода, согласованные с конструктивным пониманием математических суждений.
В частности: аппараты теории алгорифмов и обще ( теории исчислений доведены до высокого уровня тех нической оснащенности, обстоятельно исследовань связи между различными вариантами этих аппаратов огромную роль в разъяснении ряда коренных вопросов оснований математики сыграл созданный К - Геделеы конструктивный метод арифметизации формально-дедуктивных систем и арифметической интерпретации поня тия выводимости; широкую известность получили теО ремы о невозможности алгорифмов, решающих некоторые ( длительное время привлекавшие внимание математиков массовые проблемы теории логических и логико-математических исчислений, алгебры, топологии математического анализа и других разделов математики; значительные результаты достигнуты в изучении различных способов сведения одних массовых проблем к другим и в исследовании иерархии сложностей массовых проблем; введение в обиход математики разнообразных критериев сложности конструктивных объектов ( например, алгорифмов) и конструктивных процессов ( например, процессов применения алгорифмов к исходным данным привело к формированию новых многообещающих направлений исследований, уже зарекомендовавших себя серьезными результатами; шаг за шагом уточнялись и углублялись принципы конструктивного понимания математических суждений о конструктивных объектах; были разработаны и получили значительное развитие аппараты логического вывода, согласованные с конструктивным пониманием математических суждений.
В частности: аппараты теории алгорифмов и обще ( теории исчислений доведены до высокого уровня тех нической оснащенности, обстоятельно исследовань связи между различными вариантами этих аппаратов огромную роль в разъяснении ряда коренных вопросов оснований математики сыграл созданный К - Геделеы конструктивный метод арифметизации формально-дедуктивных систем и арифметической интерпретации поня тия выводимости; широкую известность получили теО ремы о невозможности алгорифмов, решающих некоторые ( длительное время привлекавшие внимание математиков массовые проблемы теории логических и логико-математических исчислений, алгебры, топологии математического анализа и других разделов математики; значительные результаты достигнуты в изучении различных способов сведения одних массовых проблем к другим и в исследовании иерархии сложностей массовых проблем; введение в обиход математики разнообразных критериев сложности конструктивных объектов ( например, алгорифмов) и конструктивных процессов ( например, процессов применения алгорифмов к исходным данным привело к формированию новых многообещающих направлений исследований, уже зарекомендовавших себя серьезными результатами; шаг за шагом уточнялись и углублялись принципы конструктивного понимания математических суждений о конструктивных объектах; были разработаны и получили значительное развитие аппараты логического вывода, согласованные с конструктивным пониманием математических суждений.
Примером может служить 10-я проблема Гильберта, состоящая в построении алгоритма, к-рый позволил бы для любого заданного многочлена с целыми коэффициентами узнать, существуют ли целые значения переменных, обращающие этот многочлен в нуль. Многие массовые проблемы долгое время не поддавались решению; впоследствии оказалось, что трудность их решения имеет принципиальный характер.
Пусть в машине Тьюринга зафиксирована какая-нибудь конфигурация. Возникает следующая массовая проблема.
Если дана некоторая библиотека ( произвольная; в этом массовость проблемы), для разделов которой составлены каталоги, то проблема составления каталога всех несамоназывающихся и только несамоназывающихся каталогов ( см. гл. Рассмотрим некоторые примеры подобных абсурдных массовых проблем.
Согласно общему принципу ( тезис Черча), интуитивная вычислимость эквивалентна частичной рекурсивно-сти функции. Отсюда вытекает, что соответствующая массовая проблема для семейства / алгоритмически разрешима, если н только если характеристическая функция Е вычислима.
Одним из свойств алгоритма является его массовость. Это означает, что алгоритм представляет собой способ решения некоторой массовой проблемы, формулируемой в виде проблемы отображения не одного, а целого множества входных слов в соответствующие им выходные слова.
В настоящее время ( к 1978) установлена неразрешимость большого числа естественных массовых проблем анализа.
Неразрешимость проблемы распознавания применимости нормального алгоритма к слову в А означает отсутствие общего метода, который для любого алгоритма и любого слова в А мог бы дать интересующий нас ответ. Ограничивая класс алгоритмов или класс обследуемых слов, или и то и другое, можно в некоторых случаях получить разрешимые массовые проблемы.
Следующее важное наблюдение в этой области состоит в том, что различные NP-проблемы можно сводить одну к другой. Под этим мы подразумеваем ( несколько расплывчато) следующее: существует полиномиальный алгоритм, который конструирует для каждой индивидуальной задачи ( или, короче ИЗ) массовой проблемы А некоторую ИЗ массовой проблемы В таким образом, что ответ на эту ИЗ проблемы А будет да в том и только том случае, когда таков же ответ на соответствующую ИЗ проблемы В. Есть несколько способов уточнить это понятие, но суть дела от этого не изменится - такое преобразование ( сведение, редукция) действительно сводит решение проблемы А к решению проблемы В. Эти преобразования используются очень часто и мы уже доказали таким способом несколько теорем в этой книге. Например, мы сводили двудольную задачу об / - факторе к задаче о потоке в разд. Очевидно, что если проблему А можно свести к проблеме В, то проблема В не может быть существенно проще, чем проблема А. Например, если существует полиномиальный алгоритм для решения проблемы В, то должен также существовать полиномиальный алгоритм, решающий проблему А.
Следующее важное наблюдение в этой области состоит в том, что различные NP-проблемы можно сводить одну к другой. Под этим мы подразумеваем ( несколько расплывчато) следующее: существует полиномиальный алгоритм, который конструирует для каждой индивидуальной задачи ( или, короче ИЗ) массовой проблемы А некоторую ИЗ массовой проблемы В таким образом, что ответ на эту ИЗ проблемы А будет да в том и только том случае, когда таков же ответ на соответствующую ИЗ проблемы В. Есть несколько способов уточнить это понятие, но суть дела от этого не изменится - такое преобразование ( сведение, редукция) действительно сводит решение проблемы А к решению проблемы В. Эти преобразования используются очень часто и мы уже доказали таким способом несколько теорем в этой книге. Например, мы сводили двудольную задачу об / - факторе к задаче о потоке в разд. Очевидно, что если проблему А можно свести к проблеме В, то проблема В не может быть существенно проще, чем проблема А. Например, если существует полиномиальный алгоритм для решения проблемы В, то должен также существовать полиномиальный алгоритм, решающий проблему А.

Не значит ли это, что неразрешимость связана с тем, что исследуемая проблема является слишком массовой. Нет, не значит, потому что, вводя ограничения на алгоритмы или на слова, или и на то и другое, можно все множество одиночных проблем, входящих в состав массовой проблемы, оставить бесконечным ( счетным), имеющим то же кардинальное число, что и исходное множество, но тем не менее получить разрешимую проблему. В некоторых случаях множество одиночных проблем неразрешимой проблемы оказывается подмножеством аналогичного множества одиночных проблем, образующих разрешимую проблему.
Конечно, логическая систематизация есть лишь одно из средств, используемых в человеческой познавательной и практической деятельности, создающей науку - это самое эффективное средство приспособления человека к среде обитания. Знаменитые результаты математической логики: теоремы о неполноте формализованных систем, включающих в себя арифметику натуральных чисел, а также о невозможности доказательства непротиворечивости таких систем средствами, формализуемыми в этих же системах; доказательство существования фрагментов дедуктивных наук, в которых имеются алгоритмически неразрешимые массовые проблемы; обнаружение невозможности формализации понятия истины, как оно используется в естественном языке, и др. - говорят о том, что при любом мыслимом прогрессе в математизации науки, при внедрении точных методов в эмпирически-описательные и экспериментальные области знания ( гуманитарные науки, биология и др.) наука в целом всегда будет носить, так сказать, двухэтажный характер: ее нижний этаж будет всегда занимать содержательная ( неформальная, неформализованная - на данной ступени развития) часть, а верхний этаж - формализованная, формальная. Взаимодействие между этими частями, основу которого составляет общественная практика, в частности техника ( технология) общества, является важной внутренней движущей силой науки.
В различных областях математики возникают проблемы, в к-рых требуется найти единую механич. Примером может служить 10-я проблема Гильберта, состоящая в построении алгоритма, к-рый позволил бы для любого заданного многочлена с целыми коэффициентами узнать, существуют ли целые значения переменных, обращающие этот многочлен в нуль. Многие массовые проблемы долгое время не поддавались решению и оказалось, что трудность их решения имеет принципиальный характер.
Понятие задачи в общем виде уточняется при помощи понятия массовой проблемы, к-рая состоит в требовании найти единый А. Ролью массовых проблем в математике и определяется как значение, так и сфера приложения понятия А.
Очевидно, чем слабее отношение эквивалентности, тем шире классу алгоритмов, эквивалентных согласно этому отношению. Естественным является стремление расширить классы эквивалентных алгоритмов, вводя более слабое определение эквивалентности. Однако при слишком слабом определении эквивалентности массовые проблемы, возникающие в теории алгоритмов, и среди них основная проблема распознавания эквивалентности алгоритмов, могут оказаться - неразрешимыми. С другой стороны, слишком сильное определение эквивалентности чрезмерно сужает классы эквивалентных алгоритмов. Правильный выбор понятия эквивалентности играет большую роль как с точки зрения возможности получения содержательных теорем, так и с точки зрения их практической применимости.
Понятие задачи в общем виде уточняется при помощи понятия массовой проблемы. Ясно поэтому что неразрешимость проблемы не дает оснований для агностич. Неразрешимость массовой проблемы означает невозможность найти соответств. Массовые проблемы чрезвычайно характерны и важны для логики и математики. Даже решение единичных проблем часто ценно именно благодаря тому, что одновременно дает общий метод для решения целого класса проблем; в то же время постановка массовой проблемы означает превращение нек-рого класса проблем в единичную проблему - проблему нахождения А. Ролью массовых проблем и определяется значение А.
Она означает лишь невозможность единого общего конструктивного метода, применимого к решению любой задачи. В математике установлено наличие алгоритмически неразрешимых массовых проблем. Встречаясь с массовой проблемой, упорно не поддающейся решению, необходимо считаться с возможностью А. Исследование такой массовой проблемы необходимо вести в двух направлениях: поиска со решения и поиска доказательства ее А. Программы, составленные для ЭЦМ, являются алгоритмами.
Она означает лишь невозможность единого общего конструктивного метода, применимого к решению любой задачи. В математике установлено наличие алгоритмически неразрешимых массовых проблем. Встречаясь с массовой проблемой, упорно не поддающейся решению, необходимо считаться с возможностью А. Исследование такой массовой проблемы необходимо вести в двух направлениях: поиска ее решения и поиска доказательства ее А. Программы, составленные для ЭЦМ, являются алгоритмами.
Понятие задачи в общем виде уточняется при помощи понятия массовой проблемы. Ясно поэтому что неразрешимость проблемы не дает оснований для агностич. Неразрешимость массовой проблемы означает невозможность найти соответств. Массовые проблемы чрезвычайно характерны и важны для логики и математики. Даже решение единичных проблем часто ценно именно благодаря тому, что одновременно дает общий метод для решения целого класса проблем; в то же время постановка массовой проблемы означает превращение нек-рого класса проблем в единичную проблему - проблему нахождения А. Ролью массовых проблем и определяется значение А.
Она означает лишь невозможность единого общего конструктивного метода, применимого к решению любой задачи. В математике установлено наличие алгоритмически неразрешимых массовых проблем. Встречаясь с массовой проблемой, упорно не поддающейся решению, необходимо считаться с возможностью А. Исследование такой массовой проблемы необходимо вести в двух направлениях: поиска со решения и поиска доказательства ее А. Программы, составленные для ЭЦМ, являются алгоритмами.
Она означает лишь невозможность единого общего конструктивного метода, применимого к решению любой задачи. В математике установлено наличие алгоритмически неразрешимых массовых проблем. Встречаясь с массовой проблемой, упорно не поддающейся решению, необходимо считаться с возможностью А. Исследование такой массовой проблемы необходимо вести в двух направлениях: поиска ее решения и поиска доказательства ее А. Программы, составленные для ЭЦМ, являются алгоритмами.
Задача найти сумму чисел 5 и 7 может служить примером одиночных проблем. Но возможна задача найти сумму целых неотрицательных чисел х и у. Это проблема массовая, содержащая одиночные проблемы в себе как частные случаи. В каком же смысле такая массовая проблема может быть решена. Ведь конкретных значений х и у мы не знаем и поэтому получить конкретное значение суммы не можем. Единственный способ решения приведенной массовой проблемы состоит в том, чтобы найти алгоритм получения суммы любых двух целых неотрицательных чисел.
А связано с выполнением бесконечной серии элементарных актов, подчиненных нек-рому ( зависящему от А) условию, причем каждый элементарный акт любой серии можно эффективно охарактеризовать нек-рым натуральным числом. J - дает вариант решения, а совокупность всех Sa образует полностью определяющий А класс РД. Если А - проблема разрешения, то соответств, класс состоит из одного элемента. Массовая проблема, для к-рой существует общекурсивная функция ( см. Рекурсивные функции и предикаты) ] А, наз. Порядка отношение) класс массовых проблем при помощи естественно вводимого понятия степени трудности ( ото делается обычным способом разбиения на классы эквивалентности, каждый из к-рых содержит взаимно сводимые массовые проблемы, причем сами эти классы и наз.
Она означает лишь невозможность единого общего конструктивного метода, применимого к решению любой задачи. В математике установлено наличие алгоритмически неразрешимых массовых проблем. Встречаясь с массовой проблемой, упорно не поддающейся решению, необходимо считаться с возможностью А. Исследование такой массовой проблемы необходимо вести в двух направлениях: поиска со решения и поиска доказательства ее А. Программы, составленные для ЭЦМ, являются алгоритмами.
Она означает лишь невозможность единого общего конструктивного метода, применимого к решению любой задачи. В математике установлено наличие алгоритмически неразрешимых массовых проблем. Встречаясь с массовой проблемой, упорно не поддающейся решению, необходимо считаться с возможностью А. Исследование такой массовой проблемы необходимо вести в двух направлениях: поиска ее решения и поиска доказательства ее А. Программы, составленные для ЭЦМ, являются алгоритмами.

Понятие задачи в общем виде уточняется при помощи понятия массовой проблемы. Ясно поэтому что неразрешимость проблемы не дает оснований для агностич. Неразрешимость массовой проблемы означает невозможность найти соответств. Массовые проблемы чрезвычайно характерны и важны для логики и математики. Даже решение единичных проблем часто ценно именно благодаря тому, что одновременно дает общий метод для решения целого класса проблем; в то же время постановка массовой проблемы означает превращение нек-рого класса проблем в единичную проблему - проблему нахождения А. Ролью массовых проблем и определяется значение А.
Понятие задачи в общем виде уточняется при помощи понятия массовой проблемы. Ясно поэтому что неразрешимость проблемы не дает оснований для агностич. Неразрешимость массовой проблемы означает невозможность найти соответств. Массовые проблемы чрезвычайно характерны и важны для логики и математики. Даже решение единичных проблем часто ценно именно благодаря тому, что одновременно дает общий метод для решения целого класса проблем; в то же время постановка массовой проблемы означает превращение нек-рого класса проблем в единичную проблему - проблему нахождения А. Ролью массовых проблем и определяется значение А.
Задача найти сумму чисел 5 и 7 может служить примером одиночных проблем. Но возможна задача найти сумму целых неотрицательных чисел х и у. Это проблема массовая, содержащая одиночные проблемы в себе как частные случаи. В каком же смысле такая массовая проблема может быть решена. Ведь конкретных значений х и у мы не знаем и поэтому получить конкретное значение суммы не можем. Единственный способ решения приведенной массовой проблемы состоит в том, чтобы найти алгоритм получения суммы любых двух целых неотрицательных чисел.
А связано с выполнением бесконечной серии элементарных актов, подчиненных нек-рому ( зависящему от А) условию, причем каждый элементарный акт любой серии можно эффективно охарактеризовать нек-рым натуральным числом. J - дает вариант решения, а совокупность всех Sa образует полностью определяющий А класс РД. Если А - проблема разрешения, то соответств, класс состоит из одного элемента. Массовая проблема, для к-рой существует общекурсивная функция ( см. Рекурсивные функции и предикаты) ] А, наз. Порядка отношение) класс массовых проблем при помощи естественно вводимого понятия степени трудности ( ото делается обычным способом разбиения на классы эквивалентности, каждый из к-рых содержит взаимно сводимые массовые проблемы, причем сами эти классы и наз.
 
Loading
на заглавную 10 самыхСловариО сайтеОбратная связь к началу страницы

© 2008 - 2014
словарь online
словарь
одноклассники
XHTML | CSS
Лицензиар ngpedia.ru
1.8.11