ПОСТА ИСЧИСЛЕНИЯ

— класс исчислений, предложенных амер. математиком Э. Л. Постом (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. М. И. Кратко.