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

условие 1), а вместо 2) - следующее условие: если элементх ш задан, предписание однозначно определяет такую последовательность преобразований, что если х обладает свойством U, то за конечное чис­ ло шагов это выясняем, если же х не обладает свойством U, то, воз­ можно, мы не сможем это выяснить за конечное число шагов. Пример эффективной процедуры. Пусть 5И^{1,2,3,...}. Число п может быть квадратом какого-либо числа из назовем это свойством и. Эффективной процедурой для выяснения, обладает ли элемент х из свойством и, может быть следующая. Берем числа и. возво­ дя их в квадраты, смотрим - равны они х либо нет. Очевидно, что та­ ким образом всегда можно выяснить для любого .v за конечное число, шагов - обладаете свойством U либо нет. Теперь рассмотрим пример полуэффективной процедуры. Рассмотрим известный процесс извлечения квадратного корня из положительных действительных чисел: л / ш = 18,1... l, 28 1 228 8 I 224 361 I 400 1 I 361 Ясно, что если для заданного числа а число 4а является рацио­ нальным, то рано или поздно заметим период. Если же Va не является рациональным числом, то, сколько бы долго нн продолжались эти вычисления, мы не сможем на их основе сказать, будет когда-нибудь период или нет, т.е. является ^fa рациональным или нет, Таким обра­ зом, эта процедура будет полуэффективной процедурой для выясне­ ния рациональности ^fa. 136