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