ИСЧИСЛЕНИЕ


ИСЧИСЛЕНИЕ

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

Пример. Рассмотрим исчисление задающее множество Мзаписей в однобуквенном алфавите {| } всех чисел вида 2n при п=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.

С. Ю. Маслов.


Математическая энциклопедия. — М.: Советская энциклопедия. . 1977—1985.

Синонимы:

Смотреть что такое "ИСЧИСЛЕНИЕ" в других словарях:

  • ИСЧИСЛЕНИЕ — (формальная система) система символов, основными компонентами которой являются: 1) алфавит (совокупность элементарных символов букв. цифр, скобок и т.п.), 2) правила построения формул из символов алфавита, 3) аксиомы (исходные доказуемые формулы) …   Философская энциклопедия

  • ИСЧИСЛЕНИЕ — ИСЧИСЛЕНИЕ, область математики, включающая в себя методы ДИФФЕРЕНЦИРОВАНИЯ и ИНТЕГРИРОВАНИЯ. Дифференциальное исчисление имеет дело с дифференцированием, т.е. процессом нахождения мгновенной скорости изменения функции в любой момент времени.… …   Научно-технический энциклопедический словарь

  • ИСЧИСЛЕНИЕ — ИСЧИСЛЕНИЕ, исчисления, ср. (книжн.). 1. Действие по гл. исчислить исчислять. Исчисление убытков. 2. Название отделов высшей математики (мат.). Диференциальное исчисление. Интегральное исчисление. Исчисление конечных плоскостей. Толковый словарь… …   Толковый словарь Ушакова

  • ИСЧИСЛЕНИЕ — знаковая система, создаваемая использованием процесса образования всех синтаксически правильных символических выражений из букв алфавита системы языка исчисления, т. е. термов (слов) и формул (фраз), и процесса вывода потенциально значимых… …   Большой Энциклопедический словарь

  • исчисление — просчитывание, эвальвация, подсчитывание, считание, подсчет, вычисление, расценивание Словарь русских синонимов. исчисление см. подсчёт Словарь синонимов русского языка. Практический справочник. М.: Русский язык. З. Е. Александрова …   Словарь синонимов

  • Исчисление — см. Считать, исчисление …   Библейская энциклопедия Брокгауза

  • исчисление — ИСЧИСЛИТЬ, лю, лишь; ленный; сов., что (книжн.). Высчитать, вычислить. И. стоимость ремонта. Толковый словарь Ожегова. С.И. Ожегов, Н.Ю. Шведова. 1949 1992 …   Толковый словарь Ожегова

  • исчисление — расчет результат оценки — [Л.Г.Суменко. Англо русский словарь по информационным технологиям. М.: ГП ЦНИИС, 2003.] Тематики информационные технологии в целом Синонимы расчетрезультат оценки EN estimate …   Справочник технического переводчика

  • Исчисление — У этого термина существуют и другие значения, см. Исчисление (значения) …   Википедия

  • исчисление — знаковая система, создаваемая использованием процесса образования всех синтаксически правильных символических выражений из букв алфавита системы  языка исчисления, то есть термов (слов) и формул (фраз), и процесса вывода потенциально значимых… …   Энциклопедический словарь

  • исчисление — основанный на четких правилах формальный аппарат оперирования со знаниями определенного вида, позволяющий дать точное описание некоторого класса задач, а для отдельных подклассов этого класса и алгоритм решения. В математической логике понятие об …   Словарь терминов логики

Книги

Другие книги по запросу «ИСЧИСЛЕНИЕ» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.