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