A Post canonical system, as created by Emil Post, is a string-manipulation system that starts with finitely-many strings and repeatedly transforms them by applying a finite set of specified rules of a certain form, thus generating a formal language. Today they are mainly of historical relevance because every Post canonical system can be reduced to a string rewriting system (semi-Thue system), which is simpler a formulation. Both formalisms are Turing complete.
Read more about Post Canonical System: Definition, Normal-form Theorem, String Rewriting Systems, Type-0 Formal Grammars
Famous quotes containing the words post, canonical and/or system:
“My business is stanching blood and feeding fainting men; my post the open field between the bullet and the hospital. I sometimes discuss the application of a compress or a wisp of hay under a broken limb, but not the bearing and merits of a political movement. I make gruel—not speeches; I write letters home for wounded soldiers, not political addresses.”
—Clara Barton (1821–1912)
“If God bestowed immortality on every man then when he made him, and he made many to whom he never purposed to give his saving grace, what did his Lordship think that God gave any man immortality with purpose only to make him capable of immortal torments? It is a hard saying, and I think cannot piously be believed. I am sure it can never be proved by the canonical Scripture.”
—Thomas Hobbes (1579–1688)
“The intellect is vagabond, and our system of education fosters restlessness. Our minds travel when our bodies are forced to stay at home. We imitate; and what is imitation but the travelling of the mind?”
—Ralph Waldo Emerson (1803–1882)