ПОСТА ИСЧИСЛЕНИЯ
— класс исчислений, предложенных амер. математиком Э. Л. Постом (1897—1954). П. и. можно рассматривать как математическое уточнение интуитивного понятия алгоритма. В этом смысле они эквивалентны другим уточнениям (см. Тьюринга машина. Нормальные алгорифмы).
П. и. наз. четверка вида 
, где А — алфавит исчисления, 
— список слов в алфавите А, называемый аксиомами, Р — алфавит переменных, причем 
список правил вывода, имеющих вид
где 
некоторые конкретные слова в алфавите 
— некоторые (не обязательно различные между собой) буквы алфавита Р.
Слово 
выводимым из слов 
по правилу (1), если для каждой переменной 
найдется такое слово в алфавите 
что, если подставить все эти слова на все места вхождения соответствующих переменных в правило (1), то подучим выражение вида
Список слов наз. выводом в исчислении 
, если каждое его слово является либо аксиомой, либо выводимо из предыдущих слов по одному из правил вывода. Слово 
выводимым в исчислении 
, если существует вывод, последним словом которого является слово D. Доказано, что любое рекурсивно-перечисленное мн-во слов в алфавите А можно получить как мн-во всех выводимых слов в подходящем П. и., имеющем только конечное число аксиом и правил вывода. Э. Пост доказал, что этот же результат справедлив для более узкого класса исчислений, т. н. нормальных канонических исчислений, все правила вывода которых имеют вид 
Вместе с тем, П. и., у которых правила вывода имеют вид — порождают только события регулярные в теории автоматов.
П. и. оказались очень удобными для сведения их к различным алгоритмическим проблемам дискретной математики и теоретической кибернетики. Тем самым была доказана алгоритмическая неразрешимость целого ряда про блем, напр., проблема тождества слов в полугруппах, проблема распознавания полноты для конечных автоматов 
др. См. Полноты проблема в теории автоматов.
Лит.: Марков А. А. Теория алгорифмов. «Труды Математического института им. В. А. Стеклова АН СССР», 1954, т. 42 [библиогр. С. 373—374]; Post Е. L. Formal reductions of the general combinatorial decision problem. «American Journal of mathematics», 1943, v. 65, № 2. М. И. Кратко.
