Post systemPostSystem2007-09-25 18:14:462009-06-18 16:38:59DefinitionPost canonical systemPost normal systemnormal productiongenerable by a Post systemPost-computable\usepackage{amssymb,amscd}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{mathrsfs}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
\usepackage{xypic}
\usepackage{pst-plot}
\usepackage{psfrag}
% define commands here
\newtheorem{prop}{Proposition}
\newtheorem{thm}{Theorem}
\newtheorem{ex}{Example}
\newcommand{\real}{\mathbb{R}}
\newcommand{\pdiff}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\mpdiff}[3]{\frac{\partial^#1 #2}{\partial #3^#1}}
\newcommand{\derive}{\stackrel{*}{\Rightarrow}}\subsubsection*{Introduction}
A \emph{Post canonical system} (or \emph{Post system} for short) $\mathfrak{P}$ is a triple $(\Sigma,X,P)$, such that
\begin{enumerate}
\item $\Sigma$ is an alphabet,
\item $X$ is an alphabet, disjoint from $\Sigma$, whose elements we call \emph{variables}, and
\item $P$ is a non-empty finite binary relation on $\Sigma^*$, the Kleene star of $P$, such that for every $(u,v)\in P$,
\begin{itemize}
\item $u\in \Sigma^*X\Sigma^*$, and
\item if $S$ is a variable occurring in $v$, then it occurs in $u$.
\end{itemize}
An element $(x,y)\in P$ is called a \emph{production} of $\mathfrak{P}$, $x$ is its \emph{antecedent}, and $y$ the \emph{consequent}. $(x,y)\in P$ is often written $x\to y$.
\end{enumerate}
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
\begin{equation}
a_1S_1a_2S_2\cdots a_nS_na_{n+1} \to b_1S_{\phi(1)}b_2S_{\phi(2)}\cdots b_mS_{\phi(m)}b_{m+1}
\end{equation}
where $a_i$ and $b_j$ are fixed words on $\Sigma$, while $S_k$ are variables, with $0<n$, $0\le m$, $m\le n$, and $\phi$ is a function (not necessarily bijective) on the set $\lbrace 1,\ldots, n\rbrace$.
\textbf{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:
\begin{itemize}
\item the antecedents in the first and fourth productions do not contain a variable
\item 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.
\end{itemize}
\textbf{Normal systems}. A Post canonical system $\mathfrak{P}=(\Sigma,X,P)$ is called a \emph{Post normal system}, or \emph{normal system} for short, if each production has the form $aS\to Sb$ (called a \emph{normal production}), where $a,b$ are words on $\Sigma$ and $S$ is a variable.
\subsubsection*{Languages generated by a Post system}
Let us fix a Post system $\mathfrak{P}=(\Sigma,X,P)$. A word $v$ is said to be \emph{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
\begin{itemize}
\item $ca^4b=caaaab\Rightarrow a^3$ if we set $V=\lambda$ and $W=U=a$, or
\item $ca^4b=caaaab\Rightarrow a^2$ if we set $V=a$ and exactly one of $W,U=a$ and the other $\lambda$.
\end{itemize}
A word $v$ is \emph{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\derive v$. Again, following from the example above, we see that $c^2abab^2\derive ac$, since $$c^2abab^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 \emph{axioms} of $\mathfrak{P}$ and elements of $T_A$ \emph{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 \emph{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^*$.
\textbf{Remarks}.
\begin{itemize}
\item If a language is generable by a Post system, it is generable by a normal system.
\item 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''.
\item 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:
\begin{displaymath}
\left\{ \begin{array}{c}
a_{11}S_{11}a_{12}S_{12}\cdots a_{1n_1}S_{1n_1}a_{1,n_1+1}, \\ \vdots \\
a_{p1}S_{p1}a_{p2}S_{p2}\cdots a_{pn_p}S_{pn_p}a_{p,n_p+1} \end{array} \right\}
\to
\left\{ \begin{array}{c}
b_{11}S_{\phi_1(1)}b_{12}S_{\phi_1(2)}\cdots b_{1m}S_{\phi_1(m_1)}b_{1,m_1+1}, \\ \vdots \\
b_{q1}S_{\phi_q(1)}b_{q2}S_{\phi_q(2)}\cdots b_{qm}S_{\phi_q(m_q)}b_{q,m+1} \end{array} \right\}
\end{displaymath}
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 \emph{each} of the antecedents by substituting the variables $S_{ij}$ by words $c_{ij}\in \Sigma^*$, and $b$ can be expressed in \emph{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!
\item It can be shown that a language is Post-generable iff it is recursively enumerable.
\end{itemize}
\subsubsection*{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 \emph{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.
\begin{thebibliography}{9}
\bibitem{md} M. Davis, {\em Computability and Unsolvability}. Dover Publications, New York (1982).
\bibitem{nc} N. Cutland, {\em Computability: An Introduction to Recursive Function Theory}. Cambridge University Press, (1980).
\bibitem{mm} M. Minsky, {\em Computation: Finite and Infinite Machines}. Prentice Hall, (1967).
\end{thebibliography}