Математическая энциклопедия - поста каноническая система

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

(*)

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

Рассматриваются различные специализации понятия П.