Introduction

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

1. $\Sigma$ is an alphabet,
2. $X$ is an alphabet, disjoint from $\Sigma$ , whose elements we call variables, and
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$ .

Examples. Let $\Sigma=\lbrace a,b,c\rbrace$ and $X=\lbrace S,U,V,W\rbrace$ . Then $(\Sigma,X,P)$ with $P$ consisting of $$aSb^2\to ba,\quad cVaWaUb\to aWU,\quad a^3cUbSW \to SabU,\quad bVa \to aV^2c$$ is a Post canonical system, while $(\Sigma,X,Y)$ with $Y$ consisting of $$ab^2\to ba,\quad cVaWaUb\to aWU,\quad aUbSc^2W \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_1u_1a_2u_2\cdots a_nu_na_{n+1} \quad\mbox{ and }\quad v=b_1a_{\phi(1)}b_2a_{\phi(2)}\cdots b_ma_{\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^4b=caaaab\Rightarrow a^3$ if we set $V=\lambda$ and $W=U=a$ , or
• $ca^4b=caaaab\Rightarrow a^2$ if we set $V=a$ and exactly one of $W,U=a$ and the other $\lambda$ .

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 semi-Thue system. In this sense, Post systems and semi-Thue 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:
  
  where each $\phi_i$ is a function from $\lbrace 1,\ldots,m_i\rbrace$ to $\lbrace (1,1),\ldots,(1,n_1),\ldots, (p,1),\ldots, (p,n_p)\rbrace$ . 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 \Sigma^*$ , and $b$ can be expressed in at least one of the consequents by the corresponding substitutions (of $S_{\phi_i(j)}$ into $c_{\phi_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 Post-generable iff it is recursively enumerable.

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):=\lbrace E(\overline{n})cE(f(\overline{n})) \mid \overline{n}\in \operatorname{dom}(f)\rbrace.$$ 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.

Bibliography

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).