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

Автор книги: авторов Коллектив

74

АЛГЕБРА ЛОГИКИ ниями буквенных переменных) и системы операций над объектами этого множества, удовлетворяющих тождествам из полной системы тождеств этого «языка». «Язык» КДО в результате такого шага абстракции превращается в «язык» т. н. булевой алгебры, «язык» УСЕ – в «язык» т. н. дистрибутивной структуры. Важным примером булевой алгебры является алгебра классов, в которой роль элементов играют подмножества (классы) некоторого фиксированного множества (т. н. универсума) ?/, роль О играет пустое множество 0, роль 1 – само U, роль AB, AvB и -Л ~ теоретико-множеств. операции пересечения, объединения и дополнения соответственно. Связь между алгеброй классов, алгеброй предикатов и алгеброй высказываний, этими тремя важнейшими интерпретациями абстрактной алгебры логики как «языка» булевой алгебры, состоит в следующем: первая переходит во вторую путем замены множеств (классов) их т. н. характеристическими предикатами (т. е. множества А – предикатом хеА, гласящим: «х принадлежит множеству А»), если при этом соответствующим образом преобразуются также операции и константы 0 и 1, а вторая переходит в третью при подстановке во все предикаты на место их аргументов некоторого фиксированного их значения. Вернее, при таком переходе от алгебры классов к алгебре предикатов получается алгебра одноместных предикатов. Другим важным случаем является алгебра двуместных предикатов, называемых чаще отношениями. С ней тесно связана алгебра отношений, отличающаяся от нее только тем, что в последней, кроме трех операций булевой алгебры, имеются еще две. Всякую булеву алгебру можно «переделать» в булево кольцо, определив операцию А+Всогласно закону X (и отбросив операцию AvB). Напр., в случае алгебры множеств роль А+В играет т. н. симметрическая разность множеств А и В (состоящая из всех тех элементов универсума, которые принадлежат одному и только одному из множеств А или В). Обратно, всякое булево кольцо (с единицей) можно «переделать» в булеву алгебру. Понятия булевой алгебры и булева кольца связываются с именем Дж. Буля. Однако оформились эти понятия (не говоря уже о терминах) значительно позже. Первые работы по алгебре логики были посвящены задачам: а) выражения логических соотношений между объемами понятий (соответственно высказываниями) в виде уравнений (равенств), б) построения алгоритмов решения логических уравнений и систем уравнений с целью автоматизировать способы извлечения из данных посылок содержащейся в них (неявно) информации (того или иного рода). В настоящее время алгебра логики развивается гл. о. под влиянием задач, встающих в области ее приложений. Она находит широкое применение в технике (особенно при решении задач, связанных с построением автоматов) и, наоборот, развивается сама под влиянием запросов техники (задач автоматизации программирования, уменьшения числа элементов в устройствах релейного действия и др.). Важную роль играют приложения в теории электрических схем, включая первоначально, начиная с работ В. И. Шестакова и К. Шеннона (30~40-е гг. 20 в.), теорию релейно-контактных схем. Вопросы, касающиеся понятий самой алгебры логики, приводят к проникновению в алгебру логики неалгебраических методов (таких, как табличные, топологические, дескриптивные) и вследствие этого к постепенному вьшелению из алгебры логики самостоятельной области – теории функций алгебры логики (или иначе, теории булевых функций). В случае более сложных схем, чем контактные, приходится часто отказываться от использования лишь обычной алгебры логики и рассматривать те или иные ее многозначные обобщения, отличные от булевых алгебр и булевых колец (см. Многозначные логики). Другим направлением современного развития алгебры логики является алгебраическая логика. Она интересна тем, что выдвигает и частично решает задачу построения алгебр неклассических логик, т.е. таких вариантов алгебры логики, которые соответствуют неклассическим исчислениям высказываний. Некоторые тенденции возможного дальнейшего развития алгебры логики как совокупности алгебраических методов логики намечаются в связи с бурным развитием ряда областей как современной алгебры, так и математической логики. Одна из них связана с мощным ростом теоретико-множественной алгебры, позволяя всякую операцию рассматривать как алгебраическую операцию. Такое рассмотрение дает возможность охватить алгебраическими методами значительную часть современной математической логики (см. Логика символическая). Другая – связана с успехами теории алгоритмов, позволившей уточнить ряд алгоритмических проблем алгебры, и последовавшим решением некоторых из них. Тенденция эта состоит в объединении алгоритмической алгебры с самой теорией алгоритмов м попытках алгебраизации последней, т.е. построения алгебраической теории алгоритмов. Эта постепенная алгебраизация все большего числа сторон математической логики будет, по-видимому, содействовать наилучшему вьшелению и ее чисто логических сторон, для того чтобы изучать последние уже иными методами. А В. Кузнецов Сокращенный вариант статьи: Алгебра логики. – В кн.: Философская энциклопедия. Т. 1. М., 1960. Как и предвидел А. Кузнецов, все большее прикладное значение приобретает теория булевых функций как самостоятельная область, выделившаяся из алгебры логики. В результате пришли к понятию функциональной системы (Рп, Q, где Рп есть множество всех функций л-значной логики (или множество всех функций счетнозначной логики PJ с заданной на нем операцией суперпозиции С. Рп обычно рассматривается как обобщение множества всех булевых функций Рт Известна содержательная трактовка понятия функциональной системы ((Рп, Q выступает ее частным случаем), в основе которой лежит рассмотрение таких пар (Р, П), в которых Р есть множество отображений, реализуемых управляющими системами из некоторого класса, a ? состоит из операции, используемой при построении новых управляющих систем из заданных. В свою очередь (Pv С) есть эквивалент алгебры логики. Таким образом, от алгебры формул, изучаемой в алгебре логики, перешли к алгебре функций. И хотя именно алгебра логики, т.е. классическая логика высказываний, лежит в основе проектирования микросхем для современной цифровой электронной техники, в том числе и для компьютеров, подобные работы ведутся и на основе многозначных логик. В частности, для функционально полных (и некоторых других) многозначных систем был построен аналог совершенной днф. Еще более важное предвидение А. Кузнецова связано с выделением алгебраической логики в одно из направлений современной алгебры логики. В первую очередь имеется в виду построение алгебр, соответствующих неклассическим логикам в том смысле, в каком булева алгебра соответствует классической логике высказываний (Rasiowa, 1974). Здесь существенным является также вопрос о построении алгебраической семантики, под которой понимается класс всех моделей некоторой алгебры, соответствующей логике L, поскольку посредством алгебраической семантики решаются такие металогические проблемы, как полнота L (относительно общезначимости в классе всех моделей), разрешимость L и др. В итоге пришли к общему вопросу о том, какая логика алгебраически представима, т.е. имеет алгебраическую семантику, а какая нет. Ответ на этот вопрос дан в работе В. Блока и Д. Пигоцци (Blok, Pigozzi, 1989). Существенно, что современное развитие алгебраической

75

АЛГОРИТМ логики представляет собой систематическое применение методов и, главное, аппарата универсальной алгебры к символической логике. Именно на это как на тенденцию возможного дальнейшего развития алгебры логики указывал А. Кузнецов, говоря о возможности «охватить алгебраическими методами значительную часть современной математической логики». Сегодня речь уже идет об алгебраическом охвате всей символической логики, и результаты здесь весьма значительны. К примеры, если Alg(L) обозначает класс алгебр, который соотносится с некоторой логикой L (если L есть классич. логика высказываний, то Alg(L) есть класс булевых алгебр), можно формулировать теоремы, утверждающие, что L имеет определенное логическое свойство тогда и только тогда (т. т. т.), когда Alg(L) имеет определенное алгебраическое свойство. Это позволяет дать алгебраическую характеризацию таких логических свойств, как полнота, наличие теоремы дедукции, компактность, разрешимость, интерполяционность Крейга, истинность формул в модели и т. д. Так, первые два свойства принимают следующий вид: L допускает строго полную гильбер– товскую аксиоматизацию (Г,_ А т. т. т., когда Г ^ А) т. т. т., когда Alg(L) есть финитно аксиоматизируемое квази-мно– гообразие; L допускает теорему дедукции (см. Дедукции теорема) т. т. т., когда Alg(L) имеет эквационально определимые главные конгруэнции. Вообще, алгебраическая логика является хорошим инструментом не только для выяснения взаимоотношения между различными логическими системами, но и для уточнения статуса логики. Лит.: Жегалкин Я. И. Арифметизация символической логики. – «Матем. сб.», т. 35. Вып. 3-4. М., 1928; Яновская С. А. основания математики и математическая логика. – В кн.: Математика в СССР за тридцать лет (1917-1947). М.-Л., 1948; Онаже. Математическая логика и основания математики. – В кн.: Математика в СССР за сорок лет (1917-1957), т. 1. М., 1959; Сб. статей по математической логике и ее приложениям к некоторым вопросам кибернетики. М., 1958; Войшвилго Е. К. Метод упрощения форм выражения функций истинности. – «Философские науки», 1958, № 2; Кузнецов А. В. Алгоритмы как операции в алгебраических системах. – «Успехи математических наук», 1958, т. 13, в. 3; Новиков П. С. Элементы математической логики. М., 1973; Биркгоф Г. Теория решеток. М., 1952; Владимиров Д. А. Булевы алгебры. 1969; Гиндикин С. Г. Алгебра логики в задачах. М., 1972; Кудрявцев В. Б. О функциональных системах. М., 1981; Яблонский С. В., Гаврилов Г. #., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М., 1966; Фридлендер Б. #., Ревякин А. М. Булева алгебра и ее применение в задачах электроники: учебное пособие. М., 1993; Algebraic logic and the methodology of applying it.—CSU Publications, 1995; Anderka H., Nemeti L, Sain L Algebraic Logic– Handbook of philosophical logic (2 ed.), forthcoming; Blok W. /., Pigozzi D. Algebraizable logics (monograph).—Memoirs of the American Mathematical Society, 1989, № 396; Font J. M., Jansana R. A general algebraic semantics for sentential logics. В., 1996; Handbook of Boolean algebras, Ed. J. D. Monk with the coop. R. Bennet, v. I—Ш. Amst., 1989; Nemeti I, Anderka H. General algebraic logic: a perspective on «What is logic».– What is logical system? Oxf., 1994; N. Y, 1995; Rasiowa H. An algebraic approach to non-classical logics. Warsz., 1974. А. С. Карпенко АЛГОРИТМ, алгоритм (от лат. algorithmi, algorismus, no имени арабского ученого 9 в. ал-Хорезми) – точное предписание, задающее потенциально осуществимый (см. Абстракция потенциальной осуществимости) вычислительный процесс (процесс исполнения алгоритма), ведущий от исходныхданных, которые могут варьировать, к конечному результату. Овладение общим методом решения точно поставленной задачи по сути дела означает знание алгоритма. Так, умение складывать два числа означает владение алгоритмом сложения чисел (напр., сложением столбиком, которому учат в школе). Необходимо различать алгоритм и алгоритмическое предписание, имеющее внешнюю форму алгоритма, но включающее не до конца определенные шаги. Так, для перевода текста с одного естественного языка на другой нельзя дать алгоритм, поскольку придется апеллировать к таким неточным понятиям, как смысл и контекст. При попытке же применения точного алгоритма получается то, что в более откровенной форме выдают машинные переводчики и в более мягкой, но от этого не менее вредной – профессиональные переводчики в тот момент, когда выходят за рамки полностью освоенных ими понятий и действий. Поскольку процесс исполнения потенциально осуществим, в теоретическом определении алгоритма отвлекаются от реальных ограничений на ресурсы и следят лишь за тем, чтобы в любой момент вычисления требуемая информация и другие ресурсы были конечными. При создании практических алгоритмов проблемы сложности выходят на первый план. Хотя неформально математики все время занимались поиском алгоритмов, данное понятие было уточнено лишь в 30-х гг. 20 в. Первыми уточнениями были абстрактные определении частично-рекурсивных и представимых функций в формальной теории чисел, появившиеся в связи с задачами доказательств теории. В 1936 Э. Пост и А. Тьюринг независимо друг от друга предложили понятия абстрактных вычислительных машин и подметили, что любой алгоритм в интуитивном смысле слова может быть реализрован на данных машинах, несмотря на кажущуюся примитивность их элементарных действий. Так, памятью машины Тьюринга является потенциально бесконечная лента, в каждой клетке которой записан символ из заранее заданного конечного алфавита. Более того, достаточно рассматривать ленту, каждая клетка которой содержит один бит информации, т.е. либо пуста, либо содержит символ |. Процессор машины Тьюринга состоит из головки, которая в любой момент обозревает одну клетку, и программы, состоящей из конечного числа команд, обычно нумеруемых натуральными числами. Каждая команда представляет собой условное действие, зависящее от символа, записанного в клетке. Это действие имеет вид совокупности элементарных инструкций формы ab(L, R, S)i, в которой присутствует лишь одна из букв Z, R, S. Z, – приказ сдвинуться на следующем такте на одну клетку влево, R – вправо, S – остаться на месте. Элементарная инструкция означает следующее: если машина видит а, записать в клетку 6, передвинуться в соответствии с командой и перейти к исполнению команды /. Такая элементарность действий машины явилась результатом проведенного Тьюрингом методологического анализа элементарных действий человека по исполнению алгоритмов. Команды машины Поста предвосхитили систему команд современных вычислительных машин. В машине имеются регистры, содержащие натуральные числа, элементарные операции увеличения и уменьшения числа на 1 и условный переход, если число в регистре равно 0. Одновременно А, Чёрч и X. Б. Карри создали одно из самых абстрактных

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. Я. К Непейвода

78

АЛЕКСАНДЕР

АЛГОРИТМИЧЕСКИЙ ЯЗЫК– искусственная система языковых средств, обладающая выразительными возможностями, достаточными для того, чтобы с ее помощью можно было задать любое принадлежащее заранее очерченному классу детерминированное общепонятное предписание, выполнение которого ведет от варьирующих в определенных пределах исходных данных к искомому результату Такого рода предписания носят название алгоритмов, откуда и сам термин «алгоритмический язык». В систематическое употребление он был введен в 1958 Г. Боттенбрухом. Исторически понятие алгоритмического языка сформировалось в 50-х гг. 20 в. в процессе становления компьютерного программирования как самостоятельной научной дисциплины. Однако теоретические истоки этого понятия прослеживаются еще в работах 30-х гг. С. К. Клини, Э. Л. Поста, А. М. Тьюринга и А. Черча по уточнению общего математического понятия алгоритма. В настоящее время теория алгоритмических языков, а также проблематика, связанная с их разработкой и использованием, составляет один из важнейших разделов информатики. В логико-лингвистическом и гносеологическом аспекте алгоритмические языки представляют собой одну из моделей императива (повелительного наклонения), и потому выступают, с одной стороны, как средство фиксации операционного знания, а с другой – как инструмент машинной, человеко-машинной или даже просто человеческой коммуникации. За короткий промежуток времени алгоритмические языки превратились в новое познавательное средство, органически вошедшее в научную и практическую деятельность человека. Обычно к ним предъявляется требование «универсальности», заключающееся в том, что должна иметься возможность моделирования с их помощью любых алгоритмов из числа тех, которые дают какое– либо уточнение общего понятия алгоритма (напр., машин Тьюринга). Абсолютная точность синтаксиса алгоритмического языка необходима не во всех случаях. Но в определенных ситуациях (напр., когда тексты, записанные на каком-либо алгоритмическом языке, начинают выступать в роли средства общения с компьютером) этот алгоритмический язык должен быть оформлен в виде соответствующего формализованного языка с четко описанным синтаксисом и точно заданной семантикой его грамматических категорий. Центральное место в таких алгоритмических языках занимают тексты, называющиеся программами (собственно говоря, именно они и выражают понятие алгоритма). Понятие программы формулируется в чисто структурных терминах синтаксиса этого языка, без какого-либо обращения в смысловым категориям. Точно такой же характер носит и описание процедуры выполнения программы. Поэтому в роли исполнителя алгоритмов, записанных на формализованных алгоритмических языках, может выступать не только человек, но и наделенное соответствующими возможностями автоматическое устройство, напр., компьютер. «Теоретические» алгоритмические языки (такие, как язык машин Тьюринга или нормальных алгорифмов Маркова) лежат в основе обшей теории алгоритмов. «Практические» алгоритмические языки – т. н. языки программирования для компьютеров (в настоящее время их известно более тысячи) – используются в практике машинного решения самых разнообразных по своему характеру задач. На ранней стадии программирования употреблялись «машинно-ориентированные» алгоритмические языки т. н. языки «низкого уровня»), учитывавшие структуру или даже характеристики конкретных вычислительных машин (систему команд, особенности и структуру памяти и т. п.). Потом им на смену пришли «проблемноориентиро– ванные» алгоритмические языки (языки «высокого уровня»), освободившие пользователя от необходимости ориентироваться на машины определенного типа и тем самым придавшие его усилиям гораздо большую математическую направленность. Дальнейшим развитием идеи алгоритмического языка явились языки программирования более общего, не обязательно алгоритмического характера. Как и алгоритмические языки, такие языки в конечном счете тоже нацелены на получение машинных программ, но во многих случаях их тексты допускают определенную свободу в выполнении и, как правило, дают лишь материал для синтеза искомых алгоритмов, а не сами эти алгоритмы. Все убыстряющееся проникновение вычислительных машин в научную, культурную и социальную сферы ведет к значительному повышению роли алгоритмических языков в жизни общества, и это выражается, в частности, в том что алгоритмы и реализующие их программы (т. е., в конечном счете, тексты на некоторых алгоритмических языках) все более и более приобретают характер реальных ресурсов экономического, научного и культурного потенциала общества, что в свою очередь вызывает к жизни значительное количество серьезных методологических и гносеологических проблем. Кроме того, все расширяющееся (вплоть до обиходного) пользование алгоритмическими языками приводит к установлению особого стиля мышления, и соотношение мышления такого рода с традиционным математическим тоже представляет собой важную и мало разработанную методологическую проблему. Лит.: Кнут Д. Искусство программирования для ЭВМ, т. 1-3. М., 1976; Ершов Л. П. Введение в теоретическое программирование: беседы о методе. М., 1977; Дейкстра Э. Дисциплина программирования. М., 1978. Н. М. Нагорный