Cтраница 4
Понятие задачи в общем виде уточняется при помощи понятия массовой проблемы. Ясно поэтому что неразрешимость проблемы не дает оснований для агностич. Неразрешимость массовой проблемы означает невозможность найти соответств. Массовые проблемы чрезвычайно характерны и важны для логики и математики. Даже решение единичных проблем часто ценно именно благодаря тому, что одновременно дает общий метод для решения целого класса проблем; в то же время постановка массовой проблемы означает превращение нек-рого класса проблем в единичную проблему - проблему нахождения А. Ролью массовых проблем и определяется значение А. [46]
Понятие задачи в общем виде уточняется при помощи понятия массовой проблемы. Ясно поэтому что неразрешимость проблемы не дает оснований для агностич. Неразрешимость массовой проблемы означает невозможность найти соответств. Массовые проблемы чрезвычайно характерны и важны для логики и математики. Даже решение единичных проблем часто ценно именно благодаря тому, что одновременно дает общий метод для решения целого класса проблем; в то же время постановка массовой проблемы означает превращение нек-рого класса проблем в единичную проблему - проблему нахождения А. Ролью массовых проблем и определяется значение А. [47]
Задача найти сумму чисел 5 и 7 может служить примером одиночных проблем. Но возможна задача найти сумму целых неотрицательных чисел х и у. Это проблема массовая, содержащая одиночные проблемы в себе как частные случаи. В каком же смысле такая массовая проблема может быть решена. Ведь конкретных значений х и у мы не знаем и поэтому получить конкретное значение суммы не можем. Единственный способ решения приведенной массовой проблемы состоит в том, чтобы найти алгоритм получения суммы любых двух целых неотрицательных чисел. [48]
А связано с выполнением бесконечной серии элементарных актов, подчиненных нек-рому ( зависящему от А) условию, причем каждый элементарный акт любой серии можно эффективно охарактеризовать нек-рым натуральным числом. J - дает вариант решения, а совокупность всех Sa образует полностью определяющий А класс РД. Если А - проблема разрешения, то соответств, класс состоит из одного элемента. Массовая проблема, для к-рой существует общекурсивная функция ( см. Рекурсивные функции и предикаты) ] А, наз. Порядка отношение) класс массовых проблем при помощи естественно вводимого понятия степени трудности ( ото делается обычным способом разбиения на классы эквивалентности, каждый из к-рых содержит взаимно сводимые массовые проблемы, причем сами эти классы и наз. [49]