Cтраница 2
Сводимость играет большую роль для обеих из указанных проблем. Сводимость задач обычно используется для того, чтобы показать, разрешима ли задача или неразрешима. Наш подход к теории разрешимости [69, 200] основан главным образом на работах Тьюринга и его модели вычислений - машине Тьюринга. Значение машины Тьюринга состоит в том, что она служит разумным представлением вычислительной машины, и можно показать1), что не существует алгоритма, который бы решал определенные проблемы машины Тьюринга, в частности проблему остановки. На основе этого был найден ряд неразрешимых задач. И важность этой теории - в том, что невозможно создать программу для ЭВМ, которая бы решала эти задачи. Следовательно, для целей практического анализа необходимо избежать этих неразрешимых задач, иначе вопросы анализа не получат ответа. [16]