Cтраница 1
Простейшая массовая проблема, посильная даже для любого ребенка ( приведена ниже), оказывается неразрешимой проблемой. Если же применить к ней волшебное свойство человека совершать неконструктивные действия, то после этого уже не нужен никакой алгоритм. [1]
Хотя массовая проблема перечисления всех экстремальных унтер-решений систем уравнений в словах алгоритмически неразрешима, для многих конкретных систем и даже для больших классов она может быть решена. [2]
Алгоритм, Массовая проблема, Разрешимое и перечислимое множества, Сводимость), исчисление Х - конверсин ( см. Оператор абстракции, Функция), логика комбинаторная и др. Из общих науч. Успехи, достигнутые в формальной теории дедукции, способствовали применению точных методов в разработке широкого комплекса проблем теории индукции и индуктивной логики ( см. ст. Логика индуктивная, раздел Современная логика индуктивная, ст. Научная индукция, Неполная индукция, Популярная индукция), и вероятностной логики. [3]
Степени трудности массовых проблем, Докл. [4]
Частным случаем массовых проблем являются разрешения проблемы. [5]
Степени трудности массовых проблем, Докл. [6]
Обратно, всякая массовая проблема, соответств. Отсюда ясна важная роль проблем разрешения. Среди проблем разрешения выделяются проблемы, поставленные для классов доказуемых формул исчислении. [7]
Такие проблемы называют также массовыми проблемами. Предписание для работы алгоритма должно быть настолько четким, чтобы эту работу можно было поручить машине. [8]
Читатель видит, что некоторые массовые проблемы, вовсе не имеющие абсурдного характера, неразрешимы потому, что из их разрешимости можно было бы вывести абсурд. Нужно заметить, что неразрешимость ( массовой) проблемы распознавания применимости нормального алгоритма в Л к слову в А совсем не означает, что мы вообще не можем распознавать применимость конкретного алгоритма к конкретному слову или к различным словам. Например, нормальный алгоритм - применим к любому слову в Л, и это сразу видно. Любой алгоритм c - v - o, где а - буква Л, тоже применим к любому слову в А. [9]
Всякий алгоритм представляет собой способ решения некоторой массовой проблемы, формулируемой в виде проблемы переработки не одного, а целого множества входных слов в соответствующие им выходные слова. Поскольку как условие, так и решение любой задачи может быть выражено в виде отдельных слов, всякий алгоритм можно рассматривать как некоторое универсальное средство для решения целого класса задач. [10]
Приведены также основные принципы доказательств алгоритмической неразрешимости некоторых простейших массовых проблем. [11]
Понятие задачи в общем виде уточняется при помощи понятия массовой проблемы, к-рая состоит в требовании найти единый А. [12]
Понятие задачи в общем виде уточняется при помощи понятия массовой проблемы. [13]
Из теоремы о неполноте но существу вытекает и существование неразрешимых массовых проблем, а именно: неразрешимой является семантнч. [14]
На основании доказанной теоремы удается установить алгоритмическую неразрешимость и некоторых других массовых проблем, возникающих в теории машин Тьюринга. При этом широко применяется метод сводимости, заключающийся в следующем. [15]