PlanetMath: Post system

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (198)
Orphanage
Unclass'd
Unproven (490)
Corrections (7)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Post system

(Definition)

Introduction

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

$\Sigma$ is an alphabet,
is an alphabet, disjoint from $\Sigma$ , whose elements we call variables, and
is a non-empty finite binary relation on $\Sigma^*$ , the Kleene star of , such that for every $(u,v)\in P$ ,
- $u\in \Sigma^*X\Sigma^*$ , and
- if is a variable occurring in , then it occurs in .
An element $(x,y)\in P$ is called a production of $\mathfrak{P}$ , is its antecedent, and the consequent. $(x,y)\in P$ is often written $x\to y$ .

The last condition basically says that in a production $x\to y$ ,

must contain at least one variable, and

can not contain any variables that are not already occurring in

. Put it more concretely, a production in a Post canonical system has the form

$\displaystyle 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}$

(1)

where

and

are fixed words on $\Sigma$ , while

are variables, with

, $0\le m$ , $m\le n$ , and $\phi$ is a function (not necessarily bijective) on the set $\lbrace 1,\ldots, n\rbrace$ .

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

$\displaystyle 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

consisting of

$\displaystyle 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 ( in the third, and 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 are words on $\Sigma$ and is a variable.

Languages generated by a Post system

Let us fix a Post system $\mathfrak{P}=(\Sigma,X,P)$ . A word is said to be immediately derivable from a word if there is a production of the form (1) above, such that

$\displaystyle u=a_1u_1a_2u_2\cdots a_nu_na_{n+1}$ and $\displaystyle \quad v=b_1a_{\phi(1)}b_2a_{\phi(2)}\cdots b_ma_{\phi(m)}b_{m+1},$

where

are words (not variables). This means that if we can write a word

in the form of an antecedent of a production by replacing all the variables with words, then we can “produce”, or “derive” a word

in the form of the corresponding consequent, replacing the corresponding variables with the corresponding words. When

is immediately derivable from

, 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 , or
$ca^4b=caaaab\Rightarrow a^2$ if we set and exactly one of and the other $\lambda$ .

A word

is derivable from a word

if there is a finite sequence of words $u_1,\ldots,u_n$ such that

$\displaystyle u=u_1\Rightarrow u_2\Rightarrow \cdots \Rightarrow u_n=v.$

When

is derivable from

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

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

Given a finite subset

of words on $\Sigma$ , let

be the set of all words derivable from words in

. Elements of

are called axioms of $\mathfrak{P}$ and elements of

theorems (of $\mathfrak{P}$ derived from axioms of

). Intuitively, we see that the Post system $\mathfrak{P}$ is a language generating machine that creates the language

via a set

of axioms. In general, we say that a language

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

of axioms on $\Sigma_1$ such that $M=T_A\cap \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 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:
$\displaystyle \left\{ \begin{array}{c} a_{11}S_{11}a_{12}S_{12}\cdots a_{1n_1}S... ...}b_{q2}S_{\phi_q(2)}\cdots b_{qm}S_{\phi_q(m_q)}b_{q,m+1} \end{array} \right\}$
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 to be immediately derivable from if can be expressed using each of the antecedents by substituting the variables $S_{ij}$ by words $c_{ij}\in \Sigma^*$ , and 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!

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

"Post system" is owned by CWoo.

(view preamble)