Post system


Introduction

A Post canonical system (or Post system for short) 𝔓 is a triple (Σ,X,P), such that

  1. 1.

    Σ is an alphabet,

  2. 2.

    X is an alphabet, disjoint from Σ, whose elements we call variables, and

  3. 3.

    P is a non-empty finite binary relationMathworldPlanetmath on Σ*, the Kleene star of P, such that for every (u,v)P,

    • uΣ*XΣ*, and

    • if S is a variable occurring in v, then it occurs in u.

    An element (x,y)P is called a production of 𝔓, x is its antecedentPlanetmathPlanetmathPlanetmath, and y the consequent. (x,y)P is often written xy.

The last condition basically says that in a production xy, 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

a1S1a2S2anSnan+1b1Sϕ(1)b2Sϕ(2)bmSϕ(m)bm+1 (1)

where ai and bj are fixed words on Σ, while Sk are variables, with 0<n, 0m, mn, and ϕ is a function (not necessarily bijectiveMathworldPlanetmathPlanetmath) on the set {1,,n}.

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

aSb2ba,cVaWaUbaWU,a3cUbSWSabU,bVaaV2c

is a Post canonical system, while (Σ,X,Y) with Y consisting of

ab2ba,cVaWaUbaWU,aUbSc2WScaV,aS

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 𝔓=(Σ,X,P) is called a Post normal system, or normal system for short, if each production has the form aSSb (called a normal production), where a,b are words on Σ and S is a variable.

Languages generated by a Post system

Let us fix a Post system 𝔓=(Σ,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=a1u1a2u2anunan+1 and v=b1aϕ(1)b2aϕ(2)bmaϕ(m)bm+1,

where ai 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 uv. Using the example above, with the production cVaWaUbaWU, we see that

  • ca4b=caaaaba3 if we set V=λ and W=U=a, or

  • ca4b=caaaaba2 if we set V=a and exactly one of W,U=a and the other λ.

A word v is derivable from a word u if there is a finite sequencePlanetmathPlanetmath of words u1,,un such that

u=u1u2un=v.

When v is derivable from u, we write u*v. Again, following from the example above, we see that c2abab2*ac, since

c2abab2=ccababbab2baac.

Given a finite subset A of words on Σ, let TA be the set of all words derivable from words in A. Elements of A are called axioms of 𝔓 and elements of TA theorems (of 𝔓 derived from axioms of A). Intuitively, we see that the Post system 𝔓 is a languagePlanetmathPlanetmath generating machine that creates the language TA via a set A of axioms. In general, we say that a language M over an alphabet Σ is generable by a Post system if there is a Post system 𝔓=(Σ1,X,P) such that ΣΣ1, a finite setMathworldPlanetmath A of axioms on Σ1 such that M=TAΣ*.

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 “equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath”.

  • 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:

    {a11S11a12S12a1n1S1n1a1,n1+1,ap1Sp1ap2Sp2apnpSpnpap,np+1}{b11Sϕ1(1)b12Sϕ1(2)b1mSϕ1(m1)b1,m1+1,bq1Sϕq(1)bq2Sϕq(2)bqmSϕq(mq)bq,m+1}

    where each ϕi is a function from {1,,mi} to {(1,1),,(1,n1),,(p,1),,(p,np)}. We may define b to be immediately derivable from a if a can be expressed using each of the antecedents by substituting the variables Sij by words cijΣ*, and b can be expressed in at least one of the consequents by the corresponding substitutions (of Sϕi(j) into cϕ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 enumerablePlanetmathPlanetmath.

Post Computability

For any positive integer m, and an m-tuple n¯:=(n1,,nm) of natural numbersMathworldPlanetmath, we may associate a word

E(n¯):=abn1abn2aabnma.

Let f:m be a partial functionMathworldPlanetmath. Define

L(f):={E(n¯)cE(f(n¯))n¯dom(f)}.

We say that f is Post-computable if L(f) is Post-generable. As expected from the last remark in the previous sectionPlanetmathPlanetmath, 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, Computability: An Introduction to Recursive FunctionMathworldPlanetmath Theory. Cambridge University Press, (1980).
  • 3 M. Minsky, Computation: Finite and InfiniteMathworldPlanetmath Machines. 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