Новая философская энциклопедия. Том первый. А - Д. - Коллектив авторов - Страница 44

76

АЛГОРИТМ понятий алгоритма: ^-определимость, выразимость с помощью терма комбинаторной логики. И ранее созданные теоретические понятия, и самые элементарные, и самые абстрактные из вновь появившихся уточнений алгоритма оказались эквивалентны. Этот факт, подтвержденный в дальнейшем для всех вновь появлявшихся точных определений алгоритма, послужил основой утверждения, скромно называемого в математике тезисом Черча, хотя степень его подтвержденное™, ныне выше, чем у любого физического «закона». Содержательное понятие алгоритма эквивалентно по объему любому из имеющихся в данным момент математических уточнений этого понятия, в частности вычислимости на машине Тьюринга. Одним из последних появилось уточнение алгоритма, наиболее близкое к современным языкам программирования, - рекурсивные схемы Скотта. Это — совокупность определений вида /.(2) <= if P(jt) then t(x) else r(x), где 3? - кортеж переменных, а сами определяемые функции могут входить в выражения Г, г. Определение понимается следующим образом: проверяется предикат Р, если он истинен, вычисляется г, иначе г. Если в вычисляемом выражении встречаются определяемые функции, они вновь по тем же правилам заменяются на их определения. Хотя по объему определяемых функций существующие уточнения понятия алгоритма эквивалентны, они различаются по своей направленности. Эти различия можно подчеркнуть, рассматривая относительные алгоритмы, строящиеся на базе некоторых абстрактных структур данных и операций над ними. Относительные алгоритмы, получающиеся на базе различных определений алгоритма, могут определять разные классы функций при одних и тех же исходных структурах и элементарных операциях. Так, напр., машины Тьюринга приводят к одним из наиболее узких определений относительных алгоритмов, а комбинаторная логика и рекурсивные схемы - наоборот, к весьма широким. При модификации машин Тьюринга разделением входной и выходной ленты (со входом можно лишь читать, на выходную — лишь писать, причем после записи и чтения мы необратимо сдвигаем ленты на одну ячейку) получается важное понятие конечного автомата, моделирующее вычислительные машины без внешней памяти. Возможности конечных автоматов значительно меньше, в частности на них нельзя распознать простые числа. С понятием алгоритма тесно связано понятие порождающего процесса, или исчисления. Порождающий процесс отличается от алгоритма тем, что он принципиально не- детерминирован, его правила суть не предписания, а разрешения выполнить некоторое действие. Примером исчисления может служить логический вывод либо разбор в формальной грамматике. Рассмотрение алгоритмов показало, что нельзя ограничиваться всюду определенными функциями и соответственно нельзя проходить мимо выражений, не имеющих значения. Ошибка является компаньоном программы. Одним из первых результатов теории апгоритмов явилась теорема о том, что не любую вычислимую функцию можно продолжить до всюду определенной вычислимой функции. Практическим примером таких функций является любой интерпретатор программ, напр., BASIC. Если не ограничивать возможности программиста, то нельзя создать интерпретатор, который невозможно было бы привести в нерабочее состояние исполнением синтаксически корректной программы. Множество, характеристическое свойство которого является всюду определенным вычислимым предикатом, называется разрешимым. Множество, принадлежность элемента которому можно установить за конечное число шагов применением некоторого алгоритма, называется перечислимым. Напр., множество тавтологий классической логики высказываний разрешимо, а множество тавтологий классической логики предикатов перечислимо. Заметим, что в случае перечислимого множества алгоритмически установить можно лишь истинность, а не ложность. В классической математике имеет место следующий критерий разрешимости: множество разрешимо, если и оно, и его дополнение перечислимы. В конструктивной этот критерий эквивалентен принципу Маркова (см. Конструктивное направление). Другая характеризация перечислимого множества - множество объектов, выводимых в некотором исчислении. Необходимо отметить, что схема вычислительного процесса на компьютере конца 20 в. - написание программы на языке высокого уровня, трансляция ее в машинный язык и исполнение компьютером — имеет теоретической основой теорему об универсальном алгоритме. При любом точном определении алгоритмов каждый алгоритм может быть задан своим определением, которое является конструктивным объектом. Этот конструктивный объект может быть алгоритмически в содержательном смысле (и при этом достаточно просто и естественно) закодирован тем видом конструктивных объектов, которые обрабатываются данными алгоритмами. Напр., определение алгоритма может быть записано как слово в некотором алфавите, а если мы взяли определение алгоритма, в котором рассматриваются лишь натуральные числа, такое слово может быть естественно представлено как число в системе счисления, основанием которой является количество букв в алфавите. Тогда имеется универсальный алгоритм ?/, перерабатывающий любую пару (ф, Р), где ср — конструктивный объект, называемый записью или программой (относительно U) алгоритма Ф, в результат применения ф к Р. Универсальный алгоритм не может быть всюду определен. Примером универсального алгоритма может служить транслятор с алгоритмического языка, в частности с Паскаля, вместе с операционной системой, исполняющей получившуюся программу. Если рассматривать лишь конструктивные объекты, то алгоритм естественно отождествить с его программой относительно некоторого U. То, что такое отождествление является ограниченным, показывают проблемы современной теории и практики программирования. Одной из самых трудных возникающих в этом случае проблем является восстановление алгоритма по реализующей его конкретной программе. Если понятие алгоритма, перерабатывающего реальные конструктивные объекты, можно считать однозначно определенным, то его обобщение на объекты высших типов допускает многочисленные варианты, неэквивалентные друг другу. Обобщение теории алгоритмов на абстрактные вычисления и объекты высших порядков является одним из основных направлений исследований современной теории алгоритмов.

77

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