смысле, в каком булева
алгебра соответствует классической логике высказываний
(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) алгоритма Ф, в результат применения ф к Р. Универсальный алгоритм не может быть всюду определен. Примером универсального алгоритма может служить транслятор с алгоритмического языка, в частности с Паскаля, вместе с операционной системой, исполняющей получившуюся программу. Если рассматривать лишь конструктивные объекты, то алгоритм естественно
