Difference between revisions of "Post production system"
From Encyclopedia of Mathematics
(Importing text file) |
(TeX) |
||
| Line 1: | Line 1: | ||
| + | {{TEX|done}} | ||
''Post normal system, Post normal calculus'' | ''Post normal system, Post normal calculus'' | ||
A particular case of a [[Post canonical system|Post canonical system]] when all derivation rules have the form | A particular case of a [[Post canonical system|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 [[#References|[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|associative calculus]] with an unsolvable word problem (Thue's problem). | and there is only one initial word (one axiom of the considered calculus). E. Post [[#References|[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|associative calculus]] with an unsolvable word problem (Thue's problem). | ||
Latest revision as of 16:25, 1 May 2014
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
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