Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Благо везде и повсюду зависит от соблюдения двух условий: 1) правильного установления конечной цели и 2) отыскания соответственных средств, ведущих к цели. Аристотель Глава 4. ДЕДУКТИВНЫЕ ТЕОРИИ § 1. Понятие об эффективных и нолуэффективных процессах (методах) Пусть имеем элементы некоторого класса М, часть из которых может обладать некоторым свойством U. Будем считать, что задан эффективный процесс (метод), если: 1) есть предписание, определяющее последовательность преобразований, которые надо применять одно за другим к элементу из М, 2) если элемент х ш задан, предписание однозначно определяет такую последовательность преобразований, что за конечное число шагов выясняем, обладает х свойством U или нет. Таким образом, если задан эффективный процесс, то для любого элемента из М за конечное число шагов выясняем, обладает заданный элемент свойством и или нет. В отличие от эффективного процесса полуэффективным процессом считается процедура, которая не всегда позволяет для произвольного элемента х из М за конечное число шагов выяснить, обладает х свойством U или нет, но если элемент х обладает заданным свойством, то процедура позволяет это выяснить. Точнее, считается, что задан полуэффективный процесс (метод), если выполняется указанное условие 1), а вместо 2) - следуюш,ее условие: если элемент х из задан, предписание однозначно определяет такую последовательность преобразований, что если х обладает свойством U, то за конечное число шагов это выясняем, если же х не обладает свойством U, то, возможно, мы не сможем это выяснить за конечное число шагов. Пример эффективной процедуры. Пусть ={1,2,3,...} . Число п может равняться квадрату какого-либо числа из М, назовем это свойством U. Эффективной процедурой для выяснения, обладает ли элемент хш М свойством и, может быть следуюш,ая. Берем числа 1,...,х и возводя их в квадраты смотрим - равны они X либо нет. Очевидно, что таким образом всегда можно выяснить для любого X за конечное число шагов - обладает х свойством U либо нет. Теперь рассмотрим пример полуэффективной процедуры. 99