Новая философская энциклопедия. Том первый. А - Д.
Шрифт:
72
АЛГЕБРА ЛОГИКИ предстоит прорасти в будущем опыте. Оно является условием функционирования «активного сознания», результирующего из действия пяти чувств и менталитета-лмлася, которое в свою очередь оставляет «отпечатки», возвращающиеся в «аккумулированное сознание» и там «прорастающие». Т. о., индивид оказывается постоянно изменяющейся конфигурацией двух взаимообусловливающих «сознаний». Помимо шести указанных видов сознания (сознания пяти чувств + ума-манаса) есть еще самосознание, характеризуемое как «загрязненный менталитет» (клишта-манас), благодаря аберрациям которого алаявиджняна мыслится как реальное эго и даже «субстанциональное Я», наподобие брахманист- ского Атмана. По Асанге, алаявиджняна является таким же кинетическим и «бессубстанциальным» феноменом, как и любой поток сознания, с теми лишь отличиями, что ему приписывается аккумулятивная функция и оно непостижимо «обычными людьми». Хотя алаявиджняна и ранее соотносилась с высшим уровнем реальности в онотологической иерархии виджнянавадинов (см. Свабхава), этот аспект концепции был наиболее обстоятельно проблематизирован у Васубандху. В «Трисвабхаванирдеше» (Экспозиция трех природ) первый уровень реальности - «воображаемый» - соответствует объектам опыта, второй - «зависимый» - субъектам, третий — совершенный - «аккумулированному сознанию». Все три носят признаки и сущего и несущего: первый уровень онтологически неопределим; второй существует не так, как является: третий является несущим по отношению у любой дуальности. Позднее эту концепцию алаявиджня- ны разрабатывают Дхармапала (Виджняптиматрасиддхи) и Дхармакирти (Праманаварттика). «Махаянасанграха» была переведена в 6 в. на китайский язык Парамартхой и стала основополагающим текстом для основанной Куйцзи школы Фасян-цзун (7-9 вв.). Китайский йогачар, историк и философ Сюань Цзан (7 в.) разработал концепцию восьмого вида сознания — того, что несет ответственность за отождествление «аккумулированного сознания» с «субстанциональным эго», не подозревая, что алаявиджняна на деле не отличается от тех «семян» будущего опыта, которые в нем хранятся. Лит.: Schmithausen L. Alayavij'nana. On the Origin and the Early Development of the Central Conception of Yogacara Philisophy, v. 1-2. Tokyo, 1987; Brown В. Е. The Buddha Nature: A Study of Tathlgatagarbha and Alayavij'nana. Delhi, 1991. В. К. Шохин АЛ-БИРУНЙ - см. Бируни. АЛ-ГАЗАЛЙ - см. /Газйли.
АЛГЕБРА ЛОГИКИ— одна из осн. частей математической логики, основанная на применении алгебраических методов к логике. Возникнув в сер. 19 в. в трудах Буля и развиваясь затем в работах Джевонса, Шредера, Пирса, Порец- кого и др., алгебра логики имела своим предметом классы (как объемы понятий), соотношения между классиками по объему и связанные с этим операции над ними. Позднее, в связи с появлением в 70-х гг 19 в. множеств теории, поглотившей часть этих задач, предмет алгебры логики значительно изменился. Основным ее предметом стали высказывания (суждения, предложения), рассматриваемые со стороны их логических значений (истина, ложь, бессмыслица и т. п.), и логические операции над ними. В основе обычной, т. н. Классической алгебры логики лежит абстракция высказывания как величины, имеющей одно (и только одно!) из двух значений: «истина» или «ложь» (короче: И. Л.) или могущей принимать оба эти значения (но не одновременно). В первом из этих случаев имеем индивидуальное высказывание (высказывание в узком, наиболее принятом смысле этого слова), во втором - высказывание-функцию. Примеры высказываний: «2-2=4 », «0<0 », «Сократ - человек», «0=1», «2*2=5», «х2=у»ч «г - человек», «Если x=yt то у=0», «Если х=2, то л^=4», «х равняется у или х не равняется у». Первые три высказывания имеют значение И (т. е. истины), 4-е и 5-е - значение Л (т. е. ложны), 6-е, 7-е, 8-е - высказывания-функции (если, напр., значениями буквенных переменных х и у могут быть целые числа, а переменной z - живые существа), 9-е и 10-е имеют значение И (при всех возможных значениях переменных х и у). Последние три из этих высказываний являются сложными, в отличие от предшествующих им простых. Абстракция в алгебре логики идет дальше. Все истинные высказывания отождествляются между собой, т. к. истинное высказывание не отличается от другого истинного высказывания по значению (от других сторон высказываний в алгебре логики отвлекаются). Ложные высказывания тоже отождествляются. При рассмотрении же высказываний-функций в алгебре
73
АЛГЕБРА ЛОГИКИ которые имеют место для операций над высказываниями. Эти законы чаще всего имеют вид тождеств, т.е. равенств, верных при вех значениях переменных. Важную роль играют тождества: 1. AB = ВА, AvB = BvA (законы коммутативности); II. (АВ)С = А(ВС), (AvB)vC=Av(BvQ (законы ассоциативности); III. A (AvB) =Л, AvAB =A (законы поглощения); IV. A(BvQ = ABvAC(закон дистрибутивности); V. А-Л = Л (закон противоречия); VI. /lv-i/1 = И (закон исключенного третьего). Эти тождества, устанавливаемые, напр., с помощью таблиц, позволяют получать другие тождества. Тождеств I - IV достаточно для того, чтобы из них по методу тождественных преобразований можно было вывести всякое (верное, конечно) тождество, левая и правая части которого - выражения алгебры логики, состоящие из переменных А, В, .., констант И, Л и знаков «•», «v», «-i» (не обязательно включая все из них). Добавление же тождеств VII А~~В = -лАчВ, А~В - ABv-тА-пВ дает возможность выводить и любые тождества, содержащие также знаки «—>», «~». Тождества V, VI, VII показывают, что константы И и Л, импликацию и эквиваленцию, рассматривая их как функции, можно выразить через конъюнкцию, дизъюнкцию и отрицание. Имеет место теорема, гласящая, что всякая функция алгебры логики может быть представлена через эти три операции, т.е. записана в виде выражения, содержащего лишь знаки этих операций и буквенные переменные. Именно, любую функцию можно записать как дизъюнкцию ФЦ, Av ..., Ап) всех выражений вида Ф(др av ..., апУ(Ага}) Ц~а2)...(Лп~яп), где flj, а2,..., ап - набор из значений И, Л. Заменяя в этой дизъюнкции выражения Л,~И на Av а А~Л - на -vi, а также стирая «коэффициенты» Ф(аг а2,..., дп), равные И (по закону WA-A) и отбрасывая члены с «коэффициентами», равными Л (по законам (Л-Л=Л, JlvA = A), мы и получим (если функция не есть константа) то выражение, о котором говорится в теореме. Дизъюнктивной нормальной формой (днф) называется выражение, которое есть буква И или Л или имеет вид А^Ар ..., vAn, где каждый член А] является либо буквенной переменной, либо ее отрицанием, либо конъюнкцией таковых, причем s не обязательно отлично от 1, т.е. знаков «v» может и не быть. Днф называется совершенной, если она есть И или Л или в каждом члене содержит ровно по одному разу все имеющиеся в ней буквы (переменные) и не имеет одинаковых членов. Всякое выражение алгебры логики можно привести к днф. А всякую днф можно привести к совершенной днф, «домно- жая» члены на недостающие буквы (по закону A=ABvA^B) и ликвидируя повторения букв в членах (по закону АА-А, А-лА- Л, Л-Л=Л, JlvA=A) и повторения членов (по закону AvA=A). Приведение к совершенной днф позволяет по любым двум данным выражениям А и В решить вопрос о том, одну ли и ту же функцию они выражают, т.е. верно ли тождество А=В. Важную роль играет т. н. сокращенная днф. Последнюю можно определить как такую днф, в к-рой 1) нет повторений букв ни в одном члене, 2) нет таких пар членов А. и А? что всякий множитель из А. имеется и в А. и 3) для всех двух таких членов, из к-рых один содержит множителем некоторую букву, а другой - отрицание той же буквы (при условии, что другой буквы, для которой это имеет место, в данной паре членов нет), имеется (в этой же днф) член, равный конъюнкции остальных множителей этих двух членов. Кроме днф, употребляются также конъюнктивные нормальные формы (кнф). Это такие выражения, к-рые можно получить из днф путем замены в них знаков «v» на «•», а «¦» на «v». Преобразованием двойственности называется такое преобразование выражения алгебры логики, при котором в этом выражении знаки всех операций заменяются на знаки двойственных им операций, а константы: И на Л, Л на И; причем операция (или функция) Ф называется двойственной для операции ?, если таблица, задающая Ф, получается из таблицы, задающей ?, путем замены в ней всюду И на Л, а Л на И (имеется в виду одновременная замена и значений функции, и значений ее аргументов). Если Ф двойственная У, а ? двойственная X, то Ф=Х. Напр., конъюнкция и дизъюнкция двойственны между собой, отрицание двойственно самому себе, константа И (как функция) двойственна константе Л. Функция ФЦ, Av ..., Ап) двойственна функции Ч!(А]УА71..., Ап), если, и только если, верно тождество -,Ф(4, А7, ...,4,) = УЫ,, -42,..., -Ч). Совершенную кнф и сокращенную кнф можно определить как такие кнф, что двойственные им выражения есть соответственно совершенная днф и сокращенная днф. Совершенные и сокращенные днф и кнф можно использовать для решения задачи обзора всех гипотез и вех следствий данного выражения алгебры логики. Причем под гипотезой выражения А алгебры логики естественно понимать такое выражение Д что В—А тождественно истинно, а под следствием выражения А - такое выражение Д что А~В тождественно истинно. Еще один, часто употребляемый в алгебре логики шаг абстракции, состоит в отождествлении И с числом 1, а Л - с числом 0. Вводится операция А+ Д задаваемая таблицей: 0+0=0,0+1=1,1+0=1,1+1=0. Она называется сложением (точнее сложением по модулю 2; другое название: разделительная дизъюнкция; читается: «А плюс В», или «А не эквивалентно В», или «Либо А, либо В»), Всякую функцию алгебры логики можно представить через умножение (т. е. конъюнкцию), сложение и константу 1 (теорема Жегал- кина). В частности, верны следующие тождества: VIII. AvB=AB+A+B,-v4=A+l IX. А-В=АВ+А+\, А~В=А+В+\. Обратные представления имеют вид X. A+B=A-nBv^AB, l=Av^A. Тождества VIII позволяют «переводить» выражения «языка» конъюнкции, дизъюнкции и отрицания (КДО) на «язык» умножения, сложения и единицы (УСЕ), а тождества X - осуществлять обратный «перевод». Тождественные преобразования можно производить и на «языке» УСЕ. В основе их лежат следующие законы: XI. АВ=ВА, А+В+В+А (законы коммутативности); XII. (АВ)С=А(ВС), (А+В)+С=А+(В+С) (ассоциативности); XIII. А(В+С)=АВ+АС (закондистрибутивности); XIV АА=А, А+(В+В)=А XV. А1=А. Этих тождеств достаточно для того, чтобы из них можно было вывести любое (верное) тождество, обе части которого суть выражения «языка» УСЕ. А добавив к ним тождества VIII, мы сможем выводить и все тождества «языка» КДО. Выражение «языка» УСЕ называется приведенным полиномом (п. п.), если оно есть 1+1 (т. е. нуль) или имеет вид A^+A7+...+As, где каждый член Ах есть либо 1, либо буквенная переменная, либо произведение последних, причем ни в одном члене нет никаких повторений букв, никакие два члена не одинаковы (в том же смысле, что и выше), a s не обязательно больше 1 (т. е. знаков «+» может не быть). Всякое выражение алгебры логики можно привести к п. п. (теорема Жегалкина). Кроме «языков» КДО и УСЕ существуют и другие «языки», обладающие тем свойством, что через операции (и константы) этих «языков» можно представить всякую функцию алгебры логики. Такие системы называются (функционально) полными. Примеры полных систем: а) конъюнкция и отрицание, б) дизъюнкция и отрицание, в) импликация и отрицание, г) импликация и 0, д) умножение, эк- виваленция и 0, е) штрих Шеффера Л|Д ж) медиана (Л, Д С), [определение: (А, Д Q=ABvACvBC\y отрицание и 1, и) медиана, эквивалента и сложение. Иногда совершают еще один важный дальнейший шаг абстракции. Отвлекаются от табличного задания операций и оттого, что значениями буквенных переменных являются высказывания. Вместо этого допускаются различные интерпретации рассматриваемого «языка», состоящие из той или иной совокупности объектов (служащих значе-
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. Н. М. Нагорный
АЛЕКСАНДЕР(Alexander) Сэмюэль (6 января 1859, Сидней - 13 сентября 1938, Манчестер) - английский философ, представитель неореализма, один из создателей эмерджентного эволюционализма (от англ. emergence — возникновение, внезапное появление). Согласно концепции Александера, Вселенная представляет собой уровни, где каждый низший уровень предшествует высшему по времени. Первичный основной вид бытия есть чистое пространство и время, а именно их элементы - точка и момент. В исходном единстве пространство и время взаимно обусловливают друг друга: без пространства «распалась бы связь времен», а без времени осталась бы бескачественная масса. Т. о., пространство выступает как связующее, как тело времени, а время как дискретность, как сознание пространства. Будучи неразрывно связаны, они образуют событие «точка-момент» без какого-либо качественного содержания. Природа на этом уровне развития есть «чистое событие», движение без качеств. Следующий уровень природы представляет собой сочетание нескольких движений, порождающих массу и инерцию, и, следовательно, имеющий уже качественное содержа-
79
АЛЕКСАНДР ние. Третья ступень есть результат сочетания механических движений, порождающих такие качества, как тепло, звук, свет и т. п. На четвертой ступени эволюции развиваются растительные и животные организмы, на пятой - дух. В этом восходящем ряду каждая низшая ступень бессознательно стремиться к высшей как к области божественного. Т. о., для доматериального бытия божественна материя, для животных и растений - человек, а для людей - некое неведомое качество, более высокое, нежели человеческая духовность. Следовательно, Божество «есть изменчивое качество и по мере того, как мир развивается во времени, Божество вместе с тем меняется». Гносеология Александера основана на неореалистическом представлении о непосредственном характере познания предмета, имманентного сознанию человека и по своему бытию независимым от индивидуального человеческого сознания, оставаясь при этом трансцендентным самому сознания ( т.е. не становясь частью его индивидуального бытия). Категории рассматриваются Александером как неизменные и постоянные свойства материи и духа. В этике защищал эволюционизм, согласно которому моральные нормы изменяются под влиянием окружающей среды. Соч.: Space, Time and Deity, vol. 1-2. L., 1927; Beauty and Other Forms of Value. L., 1933; Philosophical and Literary Pieces. L., 1939. Лит.: Богомолов A.C. Английская буржуазная философия XX века. М, 1973. Ф. Я. Блюхер