# Post system

## Introduction

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

1. 1.

$\Sigma$ is an alphabet,

2. 2.

$X$ is an alphabet, disjoint from $\Sigma$, whose elements we call variables, and

3. 3.

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

• $u\in\Sigma^{*}X\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 $\mathfrak{P}$, $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}\cdots a_{n}S_{n}a_{n+1}\to b_{1}S_{\phi(1)}b_{2}S_{\phi(2% )}\cdots b_{m}S_{\phi(m)}b_{m+1}$ (1)

where $a_{i}$ and $b_{j}$ are fixed words on $\Sigma$, while $S_{k}$ are variables, with $0, $0\leq m$, $m\leq n$, and $\phi$ is a function (not necessarily bijective   ) on the set $\{1,\ldots,n\}$.

Examples. Let $\Sigma=\{a,b,c\}$ and $X=\{S,U,V,W\}$. Then $(\Sigma,X,P)$ with $P$ consisting of

 $aSb^{2}\to ba,\quad cVaWaUb\to aWU,\quad a^{3}cUbSW\to SabU,\quad bVa\to aV^{2}c$

is a Post canonical system, while $(\Sigma,X,Y)$ with $Y$ consisting of

 $ab^{2}\to ba,\quad cVaWaUb\to aWU,\quad aUbSc^{2}W\to ScaV,\quad 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 $\mathfrak{P}=(\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 $\Sigma$ and $S$ is a variable.

## Languages generated by a Post system

Let us fix a Post system $\mathfrak{P}=(\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}\cdots a_{n}u_{n}a_{n+1}\quad\mbox{ and }\quad v=b_{1}a_% {\phi(1)}b_{2}a_{\phi(2)}\cdots b_{m}a_{\phi(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

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

• $ca^{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},\ldots,u_{n}$ such that

 $u=u_{1}\Rightarrow u_{2}\Rightarrow\cdots\Rightarrow u_{n}=v.$

When $v$ is derivable from $u$, we write $u\lx@stackrel{{\scriptstyle*}}{{\Rightarrow}}v$. Again, following from the example above, we see that $c^{2}abab^{2}\lx@stackrel{{\scriptstyle*}}{{\Rightarrow}}ac$, since

 $c^{2}abab^{2}=ccababb\Rightarrow ab^{2}\Rightarrow ba\Rightarrow ac.$

Given a finite subset $A$ of words on $\Sigma$, let $T_{A}$ be the set of all words derivable from words in $A$. Elements of $A$ are called axioms of $\mathfrak{P}$ and elements of $T_{A}$ theorems (of $\mathfrak{P}$ derived from axioms of $A$). Intuitively, we see that the Post system $\mathfrak{P}$ 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 $\Sigma$ is generable by a Post system if there is a Post system $\mathfrak{P}=(\Sigma_{1},X,P)$ such that $\Sigma\subseteq\Sigma_{1}$, a finite set  $A$ of axioms on $\Sigma_{1}$ such that $M=T_{A}\cap\Sigma^{*}$.

Remarks.

## Post Computability

For any positive integer $m$, and an $m$-tuple $\overline{n}:=(n_{1},\ldots,n_{m})$ of natural numbers  , we may associate a word

 $E(\overline{n}):=ab^{n_{1}}ab^{n_{2}}a\cdots ab^{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\operatorname{dom% }(f)\}.$

We say that $f$ is Post-computable if $L(f)$ is Post-generable. As expected from the last remark in the previous section  , a partial function is Turing-computable iff it is Post-computable.

## References

• 1 M. Davis, Computability and Unsolvability. Dover Publications, New York (1982).
• 2 N. Cutland, . Cambridge University Press, (1980).
• 3 M. Minsky, . Prentice Hall, (1967).
 Title Post system Canonical name PostSystem Date of creation 2013-03-22 17:33:28 Last modified on 2013-03-22 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 Post-computable