Namespaces
Variants
Actions

Post production system

From Encyclopedia of Mathematics
Revision as of 16:25, 1 May 2014 by Ivan (talk | contribs) (TeX)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Post normal system, Post normal calculus

A particular case of a Post canonical system when all derivation rules have the form

$$\frac{Gp}{pG}$$

and there is only one initial word (one axiom of the considered calculus). E. Post [1] has established the equivalence in the wide sense between Post production systems and Post canonical systems. Post production systems were used by Post and A.A. Markov (1947) to construct the first examples of an associative calculus with an unsolvable word problem (Thue's problem).

References

[1] E.L. Post, "Formal reductions of the general combinatorial decision problem" Amer. J. Math. , 65 : 2 (1943) pp. 197–215
[2] A.A. Markov, "Theory of algorithms" , Israel Program Sci. Transl. (1961) (Translated from Russian) (Also: Trudy Mat. Inst. Steklov. 42 (1954))


Comments

References

[a1] H.B. Curry, "Foundations of mathematical logic" , McGraw-Hill (1963)
How to Cite This Entry:
Post production system. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Post_production_system&oldid=14238
This article was adapted from an original article by S.I. Adyan (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article