Прямая и обратная функции могут сильно различаться по сложности, поэтому строить простые коды, практически не расшифровываемые без знания ключа. Это послужило основой современной практики кодирования и электронных подписей. Сложность описания системы - гораздо более сложный объект, чем само ее описание. Т. о., познать систему полностью может лишь система более высокого порядка. Минимум сложности описаний конструктивных объектов с данным числом элементов растет медленнее, чем любая вычислимая функция (т. о., есть громадные, но исключительно просто описываемые объекты, напр. 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; Дейкстра Э. Дисциплина программирования. М., 1978. Н. М. Нагорный
АЛЕКСАНДЕР(Alexander) Сэмюэль (6 января 1859, Сидней - 13 сентября 1938, Манчестер) - английский философ, представитель неореализма, один из создателей эмерджентного эволюционализма (от англ. emergence — возникновение, внезапное появление). Согласно концепции Александера, Вселенная представляет собой уровни, где каждый низший уровень предшествует высшему по времени. Первичный основной вид бытия есть чистое пространство и время, а именно их элементы - точка и момент. В исходном единстве пространство и время взаимно обусловливают друг друга: без пространства «распалась бы связь времен», а без времени осталась бы бескачественная масса. Т. о., пространство выступает как связующее, как тело времени, а время как дискретность, как сознание пространства. Будучи неразрывно связаны, они образуют событие «точка-момент» без какого-либо качественного содержания. Природа на этом уровне развития есть «чистое событие», движение без качеств. Следующий уровень природы представляет собой сочетание нескольких движений, порождающих массу и инерцию, и, следовательно, имеющий уже качественное содержа-
79
АЛЕКСАНДРние. Третья ступень есть результат сочетания механических движений, порождающих такие качества, как тепло, звук, свет и т. п. На четвертой ступени эволюции развиваются растительные и животные организмы, на пятой - дух. В