ПОСТА КАНОНИЧЕСКАЯ СИСТЕМА
- ПОСТА КАНОНИЧЕСКАЯ СИСТЕМА
, исчисление Поста,- способ задания перечислимых множеств слов. Понятие П. к. с., предложенное Э. Постом (Е. Post) в 1943, было первым общим понятием исчисления, пригодным для задания произвольных перечислимых множеств и не привязанным к логич. структуре порождаемых объектов, к их семантике и к логике вывода правил. П. к. с. задается четверкой А, Р,, p, где А - алфавит исчисления, Р(не имеющий общих букв с А) - алфавит переменных, - список слов в А(аксиом исчисления), p - список правил вывода вида
(*)
(Gij суть обозначения слов в А, р i,j - обозначения букв из Р). Слово Qполучается из Q1,. . ., Qm применением правила (*), если для каждой входящей в (*) буквы из Рможно подобрать слово в А(значение этой переменной), подставляя к-рое вместо всех вхождений рассматриваемой переменной в (*), мы получим после такого замещения всех переменных слова Q1 ,. . ., Qm - над чертой и Q - под чертой. На основе итого понимания правил определяется выводимость в П. к. с. В теории исчислений применяется следующее определение перечислимого множества слов в A, эквивалентное обычному: Мназ. перечислимым, если оно совпадает с множеством слов в А, выводимых в нек-рой П. к. с., алфавит к-рой содержит А(необходимость расширения Ахотя бы одной буквой x неустранима, но можно потребовать, чтобы помимо Мбыли выводимы лишь слова вида xQ, где Qиз А).
Рассматриваются различные специализации понятия П. <к. <с.: 1) нормальные системы Поста (все правила имеют вид ), 2) локальные исчисления (правила вида ), 3) ограниченные исчисления (алфавит однобуквенный, правила однопосылочны) и др. Упомянутые специализации предполагаются одноаксиомными, к каждой из них можно, свести произвольную П. к. с. (установленная Постом эквивалентность П. к. с. и нормальных исчислений имеет фундаментальное значение для работ этого направления, для нахождения неразрешимых систем).
Лит. см. при ст. Исчисление. С. Ю. Маслов.
Математическая энциклопедия. — М.: Советская энциклопедия.
И. М. Виноградов.
1977—1985.
Полезное
Смотреть что такое "ПОСТА КАНОНИЧЕСКАЯ СИСТЕМА" в других словарях:
ИСЧИСЛЕНИЕ — 1) Составная часть названия нек рых разделов математики, трактующих правила вычислений и оперирования с объектами того или иного типа; напр., дифференциальное И., вариационное И. 2) Дедуктивная система, т. е. способ задания множества путем… … Математическая энциклопедия
ГРАММАТИКА ПОРОЖДАЮЩАЯ — грамматика Хомского, один из видов формальной грамматики;представляет собой, по существу, частный случай исчисления Поста (см. Поста каноническая система). Систематич. изучение Г. п. было начато в 50 х гг. 20 в. Н. Хомскнм (N. Chomsky), к рый… … Математическая энциклопедия
ВЫЧИСЛИТЕЛЬНАЯ МАШИНА АБСТРАКТНАЯ — абстрактная машина, математическое понятие, к рое описывает модель вычислительной машины, абстрагируясь от ограниченности емкости запоминающих устройств и других технич. параметров вычислительных машин. В отличие от последних, В. м. а. может… … Математическая энциклопедия
ГРУЗИНСКАЯ ПРАВОСЛАВНАЯ ЦЕРКОВЬ. ЧАСТЬ II — Предстоятели ГПЦ Епископы Картли (Мцхетские): Иоанн I (20 60 е гг. IV в.); Иаков (60 70 е гг. IV в.); Иов (70 90 е гг. IV в.); Илия I (90 е гг. IV в.); Симеон I (нач. V 20 е гг. V в.); Моисей (20 е гг. V в.); Иона (20 е гг. V в.); Иеремия (20 е… … Православная энциклопедия
ХУАН ЦЗУНСИ — Хуан Тайчжун, Хуан Наньлэй, Хуан Личжоу. Выдающийся китайский философ неоконфуцианец (см. НЕОКОНФУЦИАНСТВО), общественно политический деятель и ученый энциклопедист, занимавшийся историей, географией, математикой, астрономией, теорией музыки и… … Энциклопедия Кольера
ПАКИСТАН — Исламская Республика Пакистан, государство в Южной Азии, относящееся к числу десяти самых населенных стран мира. Образовалось в 1947, когда произошел раздел Индии. Пакистан в современных границах существует с 1971. Пакистан. Столица Исламабад.… … Энциклопедия Кольера
ЕВХАРИСТИЯ. ЧАСТЬ I — [греч. Εὐχαριστία], главное таинство христ. Церкви, состоящее в преложении (μεταβολή изменение, превращение) приготовленных Даров (хлеба и разбавленного водой вина) в Тело и Кровь Христовы и причащении (κοινωνία приобщение; μετάληψις принятие)… … Православная энциклопедия
ИСТОРИЯ РУССКОЙ ЦИВИЛИЗАЦИИ — историческое развитие русской цивилизации определялось прежде всего духовно нравственными ценностями русского народа, ядром которого с принятием христианства стала Святая Русь. Однако выбор православной веры для русского народа не был случаен,… … Русская история
ИМЯСЛАВИЕ — движение почитателей имени Божия, начавшееся в рус. мон рях Афона в 1909 1913 гг. и нашедшее сторонников в России. Связанная с И. полемика нашла выражение в трудах рус. богословов и философов XX в. Имяславские споры «Афонская смута» 1909 1913 гг … Православная энциклопедия
ВЕНГРИЯ — [Венгерская Республика; венг. Magyar Köztársaság], гос во в Центр. Европе. Территория: 93 030 кв. км. Столица: Будапешт (1863 тыс. чел. 1998). Крупнейшие города: Мишкольц (182 тыс. чел. 1997), Дебрецен (210 тыс. чел. 1997), Печ (162 тыс. чел.… … Православная энциклопедия