Post system
Introduction
A Post canonical system (or Post system for short) $\U0001d513$ is a triple $(\mathrm{\Sigma},X,P)$, such that

1.
$\mathrm{\Sigma}$ is an alphabet,
 2.

3.
$P$ is a nonempty finite binary relation^{} on ${\mathrm{\Sigma}}^{*}$, the Kleene star of $P$, such that for every $(u,v)\in P$,

–
$u\in {\mathrm{\Sigma}}^{*}X{\mathrm{\Sigma}}^{*}$, and

–
if $S$ is a variable occurring in $v$, then it occurs in $u$.
An element $(x,y)\in P$ is called a production of $\U0001d513$, $x$ is its antecedent^{}, and $y$ the consequent. $(x,y)\in P$ is often written $x\to y$.

–
The last condition basically says that in a production $x\to y$, $x$ must contain at least one variable, and $y$ can not contain any variables that are not already occurring in $x$. Put it more concretely, a production in a Post canonical system has the form
$${a}_{1}{S}_{1}{a}_{2}{S}_{2}\mathrm{\cdots}{a}_{n}{S}_{n}{a}_{n+1}\to {b}_{1}{S}_{\varphi (1)}{b}_{2}{S}_{\varphi (2)}\mathrm{\cdots}{b}_{m}{S}_{\varphi (m)}{b}_{m+1}$$  (1) 
where ${a}_{i}$ and ${b}_{j}$ are fixed words on $\mathrm{\Sigma}$, while ${S}_{k}$ are variables, with $$, $0\le m$, $m\le n$, and $\varphi $ is a function (not necessarily bijective^{}) on the set $\{1,\mathrm{\dots},n\}$.
Examples. Let $\mathrm{\Sigma}=\{a,b,c\}$ and $X=\{S,U,V,W\}$. Then $(\mathrm{\Sigma},X,P)$ with $P$ consisting of
$$aS{b}^{2}\to ba,cVaWaUb\to aWU,{a}^{3}cUbSW\to SabU,bVa\to a{V}^{2}c$$ 
is a Post canonical system, while $(\mathrm{\Sigma},X,Y)$ with $Y$ consisting of
$$a{b}^{2}\to ba,cVaWaUb\to aWU,aUbS{c}^{2}W\to ScaV,a\to S$$ 
is not, for the following reasons:

•
the antecedents in the first and fourth productions do not contain a variable

•
the consequents in the third and fourth productions contain variables ($V$ in the third, and $S$ in the fourth) which do not occur in the corresponding antecedents.
Normal systems. A Post canonical system $\U0001d513=(\mathrm{\Sigma},X,P)$ is called a Post normal system, or normal system for short, if each production has the form $aS\to Sb$ (called a normal production), where $a,b$ are words on $\mathrm{\Sigma}$ and $S$ is a variable.
Languages generated by a Post system
Let us fix a Post system $\U0001d513=(\mathrm{\Sigma},X,P)$. A word $v$ is said to be immediately derivable from a word $u$ if there is a production of the form (1) above, such that
$$u={a}_{1}{u}_{1}{a}_{2}{u}_{2}\mathrm{\cdots}{a}_{n}{u}_{n}{a}_{n+1}\mathit{\hspace{1em}}\text{and}\mathit{\hspace{1em}}v={b}_{1}{a}_{\varphi (1)}{b}_{2}{a}_{\varphi (2)}\mathrm{\cdots}{b}_{m}{a}_{\varphi (m)}{b}_{m+1},$$ 
where ${a}_{i}$ are words (not variables). This means that if we can write a word $u$ in the form of an antecedent of a production by replacing all the variables with words, then we can “produce”, or “derive” a word $v$ in the form of the corresponding consequent, replacing the corresponding variables with the corresponding words. When $v$ is immediately derivable from $u$, we write $u\Rightarrow v$. Using the example above, with the production $cVaWaUb\to aWU$, we see that

•
$c{a}^{4}b=caaaab\Rightarrow {a}^{3}$ if we set $V=\lambda $ and $W=U=a$, or

•
$c{a}^{4}b=caaaab\Rightarrow {a}^{2}$ if we set $V=a$ and exactly one of $W,U=a$ and the other $\lambda $.
A word $v$ is derivable from a word $u$ if there is a finite sequence^{} of words ${u}_{1},\mathrm{\dots},{u}_{n}$ such that
$$u={u}_{1}\Rightarrow {u}_{2}\Rightarrow \mathrm{\cdots}\Rightarrow {u}_{n}=v.$$ 
When $v$ is derivable from $u$, we write $u\stackrel{*}{\Rightarrow}v$. Again, following from the example above, we see that ${c}^{2}aba{b}^{2}\stackrel{*}{\Rightarrow}ac$, since
$${c}^{2}aba{b}^{2}=ccababb\Rightarrow a{b}^{2}\Rightarrow ba\Rightarrow ac.$$ 
Given a finite subset $A$ of words on $\mathrm{\Sigma}$, let ${T}_{A}$ be the set of all words derivable from words in $A$. Elements of $A$ are called axioms of $\U0001d513$ and elements of ${T}_{A}$ theorems (of $\U0001d513$ derived from axioms of $A$). Intuitively, we see that the Post system $\U0001d513$ is a language^{} generating machine that creates the language ${T}_{A}$ via a set $A$ of axioms. In general, we say that a language $M$ over an alphabet $\mathrm{\Sigma}$ is generable by a Post system if there is a Post system $\U0001d513=({\mathrm{\Sigma}}_{1},X,P)$ such that $\mathrm{\Sigma}\subseteq {\mathrm{\Sigma}}_{1}$, a finite set^{} $A$ of axioms on ${\mathrm{\Sigma}}_{1}$ such that $M={T}_{A}\cap {\mathrm{\Sigma}}^{*}$.
Remarks.

•
If a language is generable by a Post system, it is generable by a normal system.

•
A language is generable by a Post system iff it is generable by a semiThue system. In this sense, Post systems and semiThue systems are “equivalent^{}”.

•
Instead of allowing for one antecedent and one consequent in any production, one can have a more generalized system where one production involves a finite number of antecedents as well as a finite number of consequents:
$$\left\{\begin{array}{c}\hfill {a}_{11}{S}_{11}{a}_{12}{S}_{12}\mathrm{\cdots}{a}_{1{n}_{1}}{S}_{1{n}_{1}}{a}_{1,{n}_{1}+1},\hfill \\ \hfill \mathrm{\vdots}\hfill \\ \hfill {a}_{p1}{S}_{p1}{a}_{p2}{S}_{p2}\mathrm{\cdots}{a}_{p{n}_{p}}{S}_{p{n}_{p}}{a}_{p,{n}_{p}+1}\hfill \end{array}\right\}\to \left\{\begin{array}{c}\hfill {b}_{11}{S}_{{\varphi}_{1}(1)}{b}_{12}{S}_{{\varphi}_{1}(2)}\mathrm{\cdots}{b}_{1m}{S}_{{\varphi}_{1}({m}_{1})}{b}_{1,{m}_{1}+1},\hfill \\ \hfill \mathrm{\vdots}\hfill \\ \hfill {b}_{q1}{S}_{{\varphi}_{q}(1)}{b}_{q2}{S}_{{\varphi}_{q}(2)}\mathrm{\cdots}{b}_{qm}{S}_{{\varphi}_{q}({m}_{q})}{b}_{q,m+1}\hfill \end{array}\right\}$$ where each ${\varphi}_{i}$ is a function from $\{1,\mathrm{\dots},{m}_{i}\}$ to $\{(1,1),\mathrm{\dots},(1,{n}_{1}),\mathrm{\dots},(p,1),\mathrm{\dots},(p,{n}_{p})\}$. We may define $b$ to be immediately derivable from $a$ if $a$ can be expressed using each of the antecedents by substituting the variables ${S}_{ij}$ by words ${c}_{ij}\in {\mathrm{\Sigma}}^{*}$, and $b$ can be expressed in at least one of the consequents by the corresponding substitutions (of ${S}_{{\varphi}_{i}(j)}$ into ${c}_{{\varphi}_{i}(j)}$). It can be shown that any language generated by this more general system is in fact Post generable!

•
It can be shown that a language is Postgenerable iff it is recursively enumerable^{}.
Post Computability
For any positive integer $m$, and an $m$tuple $\overline{n}:=({n}_{1},\mathrm{\dots},{n}_{m})$ of natural numbers^{}, we may associate a word
$$E(\overline{n}):=a{b}^{{n}_{1}}a{b}^{{n}_{2}}a\mathrm{\cdots}a{b}^{{n}_{m}}a.$$ 
Let $f:{\mathbb{N}}^{m}\to \mathbb{N}$ be a partial function^{}. Define
$$L(f):=\{E(\overline{n})cE(f(\overline{n}))\mid \overline{n}\in \mathrm{dom}(f)\}.$$ 
We say that $f$ is Postcomputable if $L(f)$ is Postgenerable. As expected from the last remark in the previous section^{}, a partial function is Turingcomputable iff it is Postcomputable.
References
 1 M. Davis, Computability and Unsolvability. Dover Publications, New York (1982).
 2 N. Cutland, Computability: An Introduction to Recursive Function^{} Theory. Cambridge University Press, (1980).
 3 M. Minsky, Computation: Finite and Infinite^{} Machines. Prentice Hall, (1967).
Title  Post system 
Canonical name  PostSystem 
Date of creation  20130322 17:33:28 
Last modified on  20130322 17:33:28 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  19 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 68Q42 
Classification  msc 03D03 
Synonym  normal system 
Synonym  Post generable 
Synonym  Post computable 
Related topic  FormalGrammar 
Defines  Post canonical system 
Defines  Post normal system 
Defines  normal production 
Defines  generable by a Post system 
Defines  Postcomputable 