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

Эта статья включает список ссылок , связанных материалов или внешних ссылок , но ее источники остаются неясными, поскольку в ней отсутствуют встроенные цитаты . Пожалуйста, помогите улучшить эту статью, введя более точные цитаты. ( Апрель 2021 г. ) ( Узнайте, как и когда удалять это сообщение )

Каноническая система Post , также известная как система производства Post , созданная Эмилем Постом , представляет собой систему манипуляции строками, которая начинается с конечного числа строк и многократно преобразует их, применяя конечный набор j указанных правил определенной формы, тем самым генерируя формальный язык . Сегодня они в основном имеют историческую значимость, поскольку каждая каноническая система Post может быть сведена к системе переписывания строк (полусистеме Туэ), что является более простой формулировкой. Оба формализма являются полными по Тьюрингу .

Постканоническая система представляет собой триплет ( A , I , R ), где

• A — конечный алфавит, а конечные (возможно, пустые) строки в A называются словами .
• I — конечный набор начальных слов .
• R — это конечный набор правил преобразования строк (называемых правилами продукций ), каждое правило имеет следующий вид:

${\displaystyle {\overset {\begin{matrix}g_{10}&\$_{11}&g_{11}&\$_{12}&g_{12}&\dots &\$_{1m_{1}}&g_{1m_{1}}\\g_{20}&\$_{21}&g_{21}&\$_{22}&g_{22}&\dots &\$_{2m_{2}}&g_{2m_{2}}\\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots &\vdots &\vdots \\g_{k0}&\$_{k1}&g_{k1}&\$_{k2}&g_{k2}&\dots &\$_{km_{k}}&g_{km_{k}}\\\end{matrix}}{\underset {\begin{matrix}h_{0}&\$'_{1}&h_{1}&\$'_{2}&h_{2}&\dots &\$'_{n}&h_{n}\\\end{matrix}}{\downarrow }}}}$

где каждый g и h — это указанное фиксированное слово, а каждый $ и $' — это переменная, обозначающая произвольное слово. Строки до и после стрелки в правиле производства называются антецедентами и консеквентами правила соответственно. Требуется, чтобы каждый $' в консеквенте был одним из $ s в антецедентах этого правила, и чтобы каждый антецедент и консеквент содержал по крайней мере одну переменную.

Во многих контекстах каждое правило производства имеет только один антецедент, таким образом принимая более простую форму

${\displaystyle g_{0}\ \$_{1}\ g_{1}\ \$_{2}\ g_{2}\ \точки \ \$_{м}\ g_{м}\ \rightarrow \ h_{0}\ \$'_{1}\ h_{1}\ \$'_{2}\ h_{2}\ \точки \ \$'_{н}\ h_{н}}$

Формальный язык, генерируемый канонической системой Post, — это множество, элементами которого являются исходные слова вместе со всеми словами, которые можно получить из них путем повторного применения правил производства. Такие множества являются рекурсивно перечислимыми языками, и каждый рекурсивно перечислимый язык является ограничением некоторого такого множества на подалфавит A .

Алфавит: {[, ]}Начальное слово: []Правила производства:(1) $ → [ $ ](2) $ → $$
(3) $ 1 $ 2 → $ 1 [] $ 2Образование нескольких слов в языке правильно построенных скобочных выражений: [] начальное слово [][] от (2) [[][]] от (1) [[][]][[][]] от (2) [[][]][][[][]] от (3) ...

Говорят, что постканоническая система находится в нормальной форме , если она имеет только одно начальное слово и каждое правило вывода имеет простую форму

${\displaystyle g\$\ \rightarrow \ \$h}$

Пост 1943 года доказал замечательную теорему о нормальной форме , которая применима к наиболее общему типу канонической системы Поста:

Для любой канонической системы Поста на алфавите A из нее можно построить каноническую систему Поста в нормальной форме , возможно, расширив алфавит так, чтобы набор слов, включающих только буквы A , которые генерируются системой в нормальной форме, был в точности набором слов, генерируемых исходной системой.

Системы тегов , которые включают в себя универсальную вычислительную модель, являются яркими примерами систем с нормальной формой Поста, которые также являются моногенными . (Каноническая система называется моногенной , если для любой заданной строки из нее за один шаг может быть получено не более одной новой строки — т. е. система является детерминированной.)

Система переписывания строк — это особый тип постканонической системы с одним начальным словом, а каждое произведение имеет форму

${\displaystyle P_{1}gP_{2}\ \rightarrow \ P_{1}hP_{2}}$

То есть каждое правило продукции является простым правилом подстановки, часто записываемым в виде g → h . Было доказано, что любая каноническая система Поста сводится к такой системе подстановки , которая, как формальная грамматика , также называется грамматикой фразовой структуры или грамматикой типа 0 в иерархии Хомского .

• Эмиль Пост , «Формальные редукции общей комбинаторной проблемы принятия решений», Американский журнал математики 65 (2): 197-215, 1943.
• Марвин Мински , Вычисления: конечные и бесконечные машины , Prentice-Hall, Inc., Нью-Джерси, 1967.