Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Варпаховский Ф.Л. Элементы теории алгоритмов
 
djvu / html
 

процедуры, с другой стороны, не доказана и невозможность подобной процедуры.
Пример 5. Известно, что вещественные числа подразделяются на алгебраические и трансцендентные1. Можно было бы попытаться поставить такую задачу: указать правило, позволяющее для каждого вещественного числа х в конечное число шагов определить, является это число алгебраическим или трансцендентным. То обстоятельство, что трансцендентность некоторых конкретных чисел (таких, как л или е) была установлена ценой больших усилий, не служит, понятно, принципиальным препятствием для постановки подобной задачи. Нетрудно, однако, заметить, что задача эта существенно отличается от предыдущих. В самом деле, частных задач здесь столько, сколько вещественных чисел, т. е. континуум, в то время как слов любого конечного алфавита — счетное множество. Поэтому кодирование условий задач словами какого-либо конечного алфавита в данном случае невозможно. Но если невозможно конечное кодирование условий задач, то тем более бессмысленно искать конечную процедуру для их решения. В дальнейшем такие «некорректные» задачи рассматриваться не будут.
Пример 6. При определении предикатной формулы исходными символами считаются: а) большие латинские буквы с индексами или без них (предикатные буквы); б) малые латинские буквы с индексами или без них (символы предметных переменных); с) знаки ), :=>,V,&, ~1» V, д, ( , > . Если теперь несколько видоизменить это определение, считая, что группа а) состоит из наборов Р, Р|, Р| |, . . . ,а группа б) — из наборов х, #0, xQQ, . . . , то окажется возможным каждую предикатную формулу записывать в конечном алфавите Л = {Р, |, х, О, (, ), V , &, 1, V, д, > }. Формулу
можно, например, записать следующим образом:
(((P(xf *0)) V(V*(P | (*)))) V(3*0(P | | (*0))).
Ясно, что в алфавите А можно записать предикатную формулу с любым количеством различных букв и различных предметных переменных.
1 Алгебраическими называются числа, являющиеся корнями многочленов с целыми коэффициентами, все прочие числа называются трансцендентными.

 

1 2 3 4 5 6 7 8 9 10 20


Математика