Cтраница 1
Проблема распознавания самоприменимости алгоритмически неразрешима в классе всех алгоритмов исходного алфавита операторов. [1]
Проблема распознавания самоприменимости алгоритмически неразрешима. [2]
Проблему распознавания самоприменимости можно сформулировать так: по любому шифру определить, к какому типу относится соответствующий ему алгоритм. [3]
Тогда проблема распознавания самоприменимости состоит в следующем: по любому заданному шифру установить, к какому классу относится машина. [4]
Тогда проблема распознавания самоприменимости состоит в следующем: по любому заданному шифру установить, к какому классу относится машина, зашифрованная им, - к классу самоприменимых или несамоприменимых. [5]
При доказательстве алгоритмической неразрешимости проблемы распознавания самоприменимости был использован метод от противного. С помощью этого метода доказана алгоритмическая неразрешимость множества различных проблем, в том числе и проблема эквивалентности слов для ассоциативных исчислений. [6]
Но теперь ясно, что неразрешима и проблема распознавания самоприменимости. [7]
Таким образом, предположение об алгоритмической разрешимости проблемы распознавания самоприменимости приводит к логическому противоречию и поэтому неверно. Тем самым показана алгоритмическая неразрешимость этой проблемы. [8]
Таким образом, предположение об алгоритмической разрешимости проблемы распознавания самоприменимости приводит к логическому противоречию и является поэтому неверным. Тем самым показана алгоритмическая неразрешимость этой проблемы. [9]
Это обстоятельство приводит к выводу, что алгоритмическая неразрешимость проблемы распознавания самоприменимости не является следствием узости современного точного понятия алгоритма. Если бы удалось построить точное понятие алгоритма, включающее в себя некоторые ненормализуемые алгоритмы, то проблема распознавания самоприменимости алгоритмов по-прежнему оставалась бы алгоритмически неразрешимой. [10]
Это обстоятельство приводит к выводу, что алгоритмическая неразрешимость проблемы распознавания самоприменимости не является следствием узости современного точного понятия алгоритма. Если бы удалось построить точное понятие алгоритма, включающее в себя некоторые ненормализуемые алгоритмы, то проблема распознавания самоприменимости алгоритмов по-прежнему оставалась бы алгоритмически неразрешимой. [11]
К ним относится проблема распознавания самоприменимости машин Тьюринга, проблема остановки алгоритма, проблема распознавания принадлежности числа данному нерекурсивному множеству натуральных чисел. [12]
Алгоритм В заведомо существует, значит, не может быть алгоритма А. Тем самым мы доказали, что проблема распознавания самоприменимости алгоритмически неразрешима. Отсюда вовсе не следует, что, какой бы мы ни взяли алгоритм, невозможно распознать, самоприменим ли он. [13]
В теории алгоритмов известны некоторые задачи, о которых доказано, что для их решения не существует алгоритма. Такие задачи называются алгоритмически неразрешимыми. Обычно алгоритмическая неразрешимость новых задач доказывается методом сведения к этим задачам известных алгоритмически неразрешимых задач. Тем самым доказывается, что если бы была разрешима новая задача, то можно было бы решить и заведомо неразрешимую задачу. В самом деле, если удается свести к новой задаче неразрешимую задачу, то любой алгоритм решения новой задачи решал бы и ту задачу, что противоречило бы ее неразрешимости. Применяя метод сведения, обычно ссылаются на искусственные задачи, которые не представляют самостоятельного интереса, но для которых легко непосредственно доказать их неразрешимость. К числу таких задач относится проблема распознавания самоприменимости. [14]