Поста Каноническая Система

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