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


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

Поставим теперь следующую задачу: указать способ, которой позволил бы для любой предикатной формулы установить в конечное число шагов, является эта формула тождественно истинной или нет. Каждая частная задача, соответствующая какой-либо предикатной формуле, кодируется словом, представляющим эту формулу в алфавите Л; положительные и отрицательные ответы можно кодировать, скажем, словами Р и к.
Современные исследования показали, что способа, о котором идет речь, не существует! Тонкое и кропотливое доказательство этого замечательного факта мы здесь привести не можем. Однако в дальнейшем будет рассмотрена сходная задача, решение которой позволит выяснить сущность применяемого здесь метода.
Упражнение 4. Существует ли способ для выяснения в конечное число шагов тождественной истинности произвольной пропозициональной формулы? Как следует видоизменить определение пропозициональной формулы, чтобы все такие формулы можно было бы записывать словами конечного алфавита?
Переходим к рассмотрению понятия алгоритма. Пусть задано бесконечное множество задач и каким-нибудь обр-азом указано, что понимается под решением каждой из них. Пусть далее все задачи и решения к ним записываются (кодируются) словами подходящего алфавита Л. Будем говорить, что существует алгоритм для решения данного бесконечного множества задач, если существует единый способ, позволяющий для каждой задачи этого множества в конечное число шагов найти ее решение. Иными словами, существование алгоритма означает наличие единого способа, который для каждого слова алфавита Л, кодирующего какую-нибудь задачу данного множества, позволяет в конечное число шагов найти слово алфавита Л, кодирующее решение этой задачи.
Подчеркнем еще раз, что приведенное здесь описание никоим образом не является математическим определением алгоритма, поскольку лишены математической точности выражения «единый», «конечное число шагов», фигурирующие в данном описании.
На понятие алгоритма можно взглянуть и с несколько иной точки зрения. Мы требовали, чтобы задачи данного множества задач и их решения выражались словами не-

 

1 2 3 4 5 6 7 8 9 10 20


Математика