Post production system

Show Summary Details

Quick Reference

An approach to effective computability on strings of symbols, formulated by E. L. Post. A Post production is a string rewriting rule. A set L of strings is said to be Post-generable if there exists a finite set of strings, called axioms, and a finite set P of Post productions such that each string in the set can be obtained from the axiom set by some finite derivation, where each step in the derivation is sanctioned by an application of some production in P. It turns out that the class of Post-generable sets on some fixed alphabet A is exactly the class of recursively enumerable sets, order A.

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.