ИСЧИСЛЕНИЕ

Значение ИСЧИСЛЕНИЕ в математической энциклопедии:

- 1) Составная часть названия нек-рых разделов математики, трактующих правила вычислений и оперирования с объектами того или иного типа; напр., дифференциальное И., вариационное И. 2) Дедуктивная система, т. е. способ задания множества путем указания исходных элементов (аксиом исчисления) и вывода правил, каждое из к-рых описывает, как строить новые элементы из исходных и уже построенных. Выводомв И. наз. такое линейно упорядоченное множество, что всякий его элемент Рявляется либо аксиомой И. либо заключением применения к.-л. принадлежащего правила вывода, причем все посылки этого применения предшествуют Рв выводе. Элемент наз. выводимым в если в можно построить вывод, кончающийся этим элементом. Для удобства изучения выводов они иногда записываются в виде нелинейной структуры (см. Вывода дерево);выводы могут быть снабжены анализом, т. е. дополнительной информацией, облегчающей проверку правильности вывода (напр., при каждом элементе вывода пишутся код правила и номера предшествующих элементов, при помощи к-рых получен данный элемент).

Пример. Рассмотрим исчисление задающее множество Мзаписей в однобуквенном алфавите {| } всех чисел вида 2ⁿ при п=1, 2, ... И. имеет одну аксиому || и одно правило вывода "Из слова Рможно получить РР". Легко убедиться, что слова из Ми только они выводимы в

И. может иногда порождать также нек-рые вспомогательные элементы, в таком случае задается нек-рый алгоритм, позволяющий отличать основные элементы от вспомогательных. При отсутствии вспомогательных элементов говорят о строгом представлении множества Мисчислением Таков, в частности, приведенный выше пример.

Используются и более сложные формы задания множеств посредством И., когда вместо элементов множества порождаются их коды (т. е. нужен еще дополнительный алгоритм, декодирующий основные элементы). Так, широко распространены кодировки нелинейных объектов словами, кодировки слов и n-к чисел натуральными числами и др. Важным частным случаем нестрогого представления является ступенчатое построение П., когда выводимые объекты предыдущих ступеней носят вспомогательный характер при формировании следующей ступени (такие построения особенно характерны для логико-математич. теорий, к-рые оказываются верхней ступенью над рядом И., задающих язык теории).

Понятие И. является формализацией интуитивного представления об индуктивно порождаемом множестве. Такие множества широко используются в математике; в частности, формализация любой развитой теории опирается на большое количество индуктивно определяемых множеств, начиная с простейших (множества переменных, термов, формул и т. п.) и кончая множеством теорем, к-рые выводятся из аксиом теории при помощи соответствующих логич. переходов. Неудивительно поэтому, что И. являются одним из основных аппаратов математич. логики. Именно логические исчисления были первыми примерами полностью формализованных дедуктивных систем (на базе этих И. вырабатывались основные понятия и методы общей теории И., возникли далеко идущие обобщения И.; см., напр., Карнапа правило). Нек-рые специальные виды И. хорошо пригодны для описания формальных грамматик (чем определяется роль И. в математической лингвистике )и для задания множеств, распознаваемых автоматами конечными.

Одной из основных сфер применения общей теории И. является алгоритмов теория. Это объясняется тем, что понятие И. имеет такой же фундаментальный характер, как и понятие алгоритма. Действительно, класс множеств, к-рые могут быть заданы при помощи И., совпадает с классом алгоритмически перечислимых множеств слов (если оставаться в рамках общепринятых уточнений понятия И. и не прибегать к обобщениям, нарушающим потенциальную возможность порождения каждого выводимого элемента). Отсюда вытекает существование такого И., для к-рого неразрешима проблема выводимости, т. е. невозможен алгоритм, к-рый для всех слов (в языке И.) кончал бы работу с правильным ответом (напр., давал бы 0 на всех выводимых словах и 1 на остальных). Из возможности задания сколь угодно сложных перечислимых множеств вытекает также существование универсальных в том или ином смысле И. (т. е . И., моделирующих все другие И. фиксированного языка, см. Креативное множество). Эти факты, в сочетании с изучением различных модификаций и специализаций общего понятия И., открывают возможности получения интересных алгоритмически неразрешимых проблем. Основополагающее значение для этого направления имела работа Э. Поста (см. [1]), в к-рой впервые было предложено понятие дедуктивной системы, пригодной для порождения произвольных перечислимых множеств слов (см. Поста каноническая система). Широкие возможности в оформлении правил вывода канонических И. позволяют хорошо обслуживать процессы индуктивного порождения множеств; подавляющее большинство построенных конкретных И. легко и естественно можно сформулировать как частные случаи канонических И.

Ассоциативные исчисления, называемые также системами Туэ, служат удобным средством задания и изучения групп и полугрупп.

Лит.:[1] Post E. L., "Amer. J. Math.", 1943, v. 65, № 2, p. 197-215; [2] Марков А. А., Теория алгорифмов, M.- Л., 1954 ("Тр. матем. ин-та АН СССР", т. 42); [3] "Тр. матем. ин-та АН СССР", 1964, т. 72, с. 5-56; 1967,т. 93, с. 3-42.

С. Ю. Маслов.