Новая философская энциклопедия. Том первый

АЛГОРИТМ Другим важнейшим направлением развития теории алгоритмов служит теория сложности вычислений, рассматривающая проблемы оценки ресурсов, необходимых для работы алгоритмов. Основы ее закладывали российские ученые А, Н. Колмогоров и А. А. Марков и венгерский математик С. Кальмар. Вот некоторые из ее результатов, имеющих методологическое значение. Имеются два типа сложности — сложность определения и сложность вычислений. Они раскрывают разные стороны исследуемых методов и объектов, хотя между ними имеются некоторые зависимости. В частности, чем быстрее вычисление алгоритма, определяющего некоторый объект, тем, как правило, сложнее его описание. Во многих практических случаях, напр., для сортировки данных, приходится искать компромисс и использовать не самые быстрые теоретически, хотя и более простые в действии алгоритмы. Если сложность определения практически не зависит от конкретного уточнения понятия алгоритма, то число шагов и используемая память резко различаются, напр., для рекурсивных схем и машин Тьюринга. Самое простое понятие машин Тьюринга оказалось наиболее подходящим для теоретического анализа вычислительной сложности задач. Число шагов и используемая память - взаимозависимые характеристики вычислительного процесса. Часто удается убыстрить процесс, задействовав больше памяти, либо уменьшить память, увеличив число шагов процесса. Но такая оптимизация ресурсов возможна лишь в ограниченных пределах, и более критическим является число шагов. Память теоретически можно неограниченно уменьшать, замедляя программу (конечно же она тем не менее растет с ростом исходных данных, но не более чем линейно). Имеются и такие случаи, когда за счет сложности описания алгоритма можно неограниченно убыстрять процесс вычисления (теорема об ускорении). Тем не менее практически и здесь быстро наступает предел ввиду неустойчивости работы сложных алгоритмов. Практически вычислимыми оказываются функции, число шагов вычисления которых на машине Тьюринга может быть оценено некоторым многочленом от длины исходных данных. Степень данного многочлена определяет объем исходных данных, которые могут быть обработаны. В частности, для вычислений часто приемлемы алгоритмы, число шагов которых растет как четвертая степень от исходных данных, а для работы с большими базами данных обычно неприемлемы даже квадратично растущие алгоритмы. Экспоненциальный рост числа шагов машины Тьюринга означает, что область реального применения данного алгоритма жестко ограничена сверху и никакой рост вычислительных ресурсов не может значительно поднять планку. Напр., для увеличения числа булевых переменных в проверяемой пропорциональной формуле на 1 придется поднимать быстродействие машины в два раза. Более чем экспоненциальный рост означает практическую невычислимость. Прямая и обратная функции могут сильно различаться по сложности, поэтому строить простые коды, практически не расшифровываемые без знания ключа. Это послужило основой современной практики кодирования и электронных подписей. Сложность описания системы - гораздо более сложный объект, чем само ее описание. Т. о., познать систему полностью может лишь система более высокого порядка. Минимум сложности описаний конструктивных объектов с данным числом элементов растет медленнее, чем любая вычислимая функция (т. о., есть громадные, но исключительно просто описываемые объекты, напр. 1010 ). Сложность описания большинства объектов данной длины не намного ниже, чем длина записи этих объектов. Т. о., возникает понятие содержательного случайного объекта, не описываемого кратко никакими алгоритмическими средствами. На основе теории сложности описания А. Н. Колмогоров, Л. А. Левин, П. Мартин-Леф и другие развили алгоритмическую теорию вероятностей. Основой данной теории явилось содержательное определение случайной последовательности по Р. Мизесу. Двоичная последовательность случайна, если из нее нельзя выбрать никакую последовательность с другой частотой нулей и единиц. Напр., последовательность 0, 1,0, 1... неслучайна, поскольку последовательность ее четных членов состоит из одних единиц. В классической математике такое определение пусто. А. Н. Колмогоров уточнил его, предложив рассматривать лишь алгоритмические перестановки подмножеств членов данной последовательности. Оказалось, что случайность связана со сложностью определения. Сложность фрагментов случайной последовательности пропорциональна длине их записи. Итак, содержательно случайные объекты являются приближениями к случайным последовательностям. Для любой совокупности программ, имеющих ограниченную сложность, можно построить ограниченный универсальный алгоритм, исполняющий все их без ошибок, но его сложность будет неизмеримо выше, чем сложность исполняемых программ. Далее, можно построить алгоритмический процесс, расширяющий ограниченный универсальный алгоритм с тем, чтобы включить любую предъявленную программу, не входящую в данный класс, но при этом сложность универсального метода станет еще выше. Уже один шаг данного процесса диагонализации далеко выводит за рамки класса функций, считающихся реально вычислимыми. Это — алгоритмическая основа софизма, примененного в аргументе Саймона (см. Парадокс логический). Заметим, что тезис Черча содержит одно важное онтологическое предположение: о невозможности обозреть вечность. Поэтому в общей теории относительности (в частности, во вселенной Геделя, в которой время может ходить по кругу) имеются миры, в которых, пролетая сквозь вращающуюся черную дыру, можно вычислить алгоритмически невычислимую функцию. Класс функций, которые могут быть вычислены в таких Вселенных, называется гиперарифметическим. Он неопределим в арифметике и определим лишь в анализе. Лит.: Клини С. К. Введение в метаматематику. М., 1957; Баренд- регт X. ^-исчисление. Его синтаксис и семантика. М., 1984; Марков А. А., Нагорный H М. Теория алгоритмов. М., 1984; Теория рекурсий. - В кн.: Справочная книга по математической логике. М., 1982; Успенский В. А., Семенов А Л. Теория алгоритмов: основные открытия и приложения. М., 1987; Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М., 1972; Непейвода H. Н. Прикладная логика. Ижевск, 1997. Я. К Непейвода