ПОСТА КАНОНИЧЕСКАЯ СИСТЕМА

Значение ПОСТА КАНОНИЧЕСКАЯ СИСТЕМА в математической энциклопедии:

, исчисление Поста,- способ задания перечислимых множеств слов. Понятие П. к. с., предложенное Э. Постом (Е. Post) в 1943, было первым общим понятием исчисления, пригодным для задания произвольных перечислимых множеств и не привязанным к логич. структуре порождаемых объектов, к их семантике и к логике вывода правил. П. к. с. задается четверкой А, Р,, p, где А - алфавит исчисления, Р(не имеющий общих букв с А) - алфавит переменных, - список слов в А(аксиом исчисления), p - список правил вывода вида

(*)

(G_ij суть обозначения слов в А, р _i,j - обозначения букв из Р). Слово Qполучается из Q₁,. . ., Q_m применением правила (*), если для каждой входящей в (*) буквы из Рможно подобрать слово в А(значение этой переменной), подставляя к-рое вместо всех вхождений рассматриваемой переменной в (*), мы получим после такого замещения всех переменных слова Q₁,. . ., Q_m - над чертой и Q - под чертой. На основе итого понимания правил определяется выводимость в П. к. с. В теории исчислений применяется следующее определение перечислимого множества слов в A, эквивалентное обычному: Мназ. перечислимым, если оно совпадает с множеством слов в А, выводимых в нек-рой П. к. с., алфавит к-рой содержит А(необходимость расширения Ахотя бы одной буквой x неустранима, но можно потребовать, чтобы помимо Мбыли выводимы лишь слова вида xQ, где Qиз А).

Рассматриваются различные специализации понятия П. <к. <с.: 1) нормальные системы Поста (все правила имеют вид ), 2) локальные исчисления (правила вида ), 3) ограниченные исчисления (алфавит однобуквенный, правила однопосылочны) и др. Упомянутые специализации предполагаются одноаксиомными, к каждой из них можно, свести произвольную П. к. с. (установленная Постом эквивалентность П. к. с. и нормальных исчислений имеет фундаментальное значение для работ этого направления, для нахождения неразрешимых систем).

Лит. см. при ст. Исчисление. С. Ю. Маслов.