Математическая логика и теория алгоритмов

Благо везде ii повсюду зависит от соблюденш двух условий: I) правшьного установления конечной цели и 2) отыскания соответственных средств, ведущих к цели. Аристотель Гл а в а 4. ДЕДУКТИВНЫЕ ТЕОРИИ § 1. Понятие об эффективных и полуэффективных процессах (методах) Пусть имеем элементы некоторого класса 94., часть из которых может обладать некоторым свойством U. Будем считать, что задан э ф ф е к т и в н ы й n p o i i e c c (метод), если; 1) есть предписание, опреде­ ляющее последовательность преобразований, которые надо применять одно за другим к элементу из М] 2) если элемент х из М задан, предпи­ сание однозначно определяет такую последовательность преобразова­ ний, что за конечное число шагов выясняем, обладает х свойством u или нет. Таким образом, если задан эффективный процесс, то для любого элемента из М за конечное число шагов выясняем, обладает заданный элемент свойством u или нет. В отличие от эффективного процесса полуэффективньтпро­ ц е с с о м считается некоторая процедура, которая не всегда позволяет для произвольного элемента х из iW за конечное число шагов выяс­ нить, обладает х свойством u или нет. Точнее будем считать, что задан полуэффективный процесс (метод), если выполняется указанное 135