ИСЧИСЛЕНИЕ, дедуктивная система
— система, задающая множество путем указания исходных элементов (аксиом) и правил вывода, каждое из которых описывает способ построения новых элементов из исходных и уже построенных. Каждое применение правила вывода по множеству элементов, называемых посылками этого применения, дает элемент, называемый заключением этого применения (в большинстве изучавшихся И. всякое применение правила вывода имеет лишь конечное число посылок). Выводом в И.
такое линейно упорядоченное множество, что всякий его элемент Р является аксиомой из S или заключением применения какого-нибудь принадлежащего S правила вывода, причем все посылки этого применения предшествуют Р в выводе. Элемент наз. выводимым в S, если в S можно построить вывод, кончающийся этим элементом. Пример. Для задания мн-ва слов вида
можно предложить И. А с двумя аксиомами 
и с двумя правилами вывода — «от слова вида Р Q разрешается перейти к слову вида 
и «от слов вида Р и Р Q разрешается перейти к слову 
Все элементы, выводимые в А, имеют либо вид (1), либо вид 
причем все слова указанных двух видов выводимы. В примере проявляется характерная
черта способа задания мн-в посредством И.: построенное И. может порождать, помимо интересующего нас мн-ва, некоторые вспомогательные элементы, которые можно отличить от осн. элементов при помощи некоторого алгоритма. Обычно такой алгоритм сравнительно прост; в рассмотренном примере это алгоритм, проверяющий наличие в слове буквы.
Важная роль И. определяется тем, что индуктивно порождаемые мн-ва широко используются в математике. В частности, формализация любой развитой матем. теории опирается на большое к-во индуктивно определяемых мн-в, начиная от простейших, задающих язык теории (переменные, числа, формулы и т. п.), и кончая мн-вом теорем, которые выводятся из аксиом теории при помощи логич. средств, характерных для теории. Поэтому И. являются одним из осн. аппаратов логики математической. Некоторые спец. виды И. предназначены для описания грамматик и для задания множеств, распознаваемых автоматами конечными. Общее понятие И. применяют в алгоритмов теории. Это объясняется тем, что понятие «исчисление» имеет такой же фундаментальный характер, как и понятие «алгоритм». Действительно, формализация понятия индуктивно порождаемого мн-ва дает нам тот же класс алгоритмически перечислимых мн-в, который мы получили бы, положив в основу определения любое общепринятое уточнение понятия алгоритма (первую такую формализацию — т. н. канонические И. предложил амер. математик Э. Л. Пост в 1943). Отсюда вытекает существование такого И. 2, для которого проблема выводимости неразрешима, т. е. невозможен алгоритм, кончающий работу для любого слова Р в зафиксированном алфавите (алфавите И. 2) и распознающий, выводимо ли Р в 2. Этот факт, в сочетании с изучением различных модификаций и специализаций общего понятия И., открывает широкие возможности для получения интересных алгоритмически неразрешимых проблем. Основополагающее значение для работ этого направления имеет результат Поста о возможности задания любого перечислимого мн-ва посредством нормального И. Нормальное И. — это И., выводимыми элементами которого являются слова некоторого алфавита А, имеющие одну аксиому и конечное число правил вывода следующей структуры: «из слова вида GP выводимо слово Р С» (где G и 
фиксированные слова в А, Р — произвольное слово в 4).
Аппарат И. может оказаться полезным при изучении различных объектов, которые по своим рабочим возможностям аналогичны алгоритмам, но не обязательно должны быть детерминированными в работе. Термин «И.» применяется еще В качестве составной части названия некоторых разделов математики, трактующих правила вычислений и оперирования с объектами того или иного типа, напр., дифференциальное И., вариационное И.
Лит.: Цейтин Г. С. Один способ изложения теории алгоритмов и перечислимых множеств. «Труды Математического института им. В. А. Стеклова АН СССР», 1964, т. 72; Кратко М. И. Формальные исчисления Поста и конечные автоматы. «Проблемы кибернетики», 1966, № 17; Маслов С. Ю. Понятие строгой представимости в общей теории исчислений. «Труды Математического института им. В. А. Стеклова АН СССР», 1967, т, 93; Post Е. L. Formal reductions of the general combinatorial decision problem. «American lournal of mathematics», 1943, v. 65, Jsis 2. С. Ю. Маслов.
