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:
“A demanding stranger arrived one morning in a small town and asked a boy on the sidewalk of the main street, “Boy, where’s the post office?”
“I don’t know.”
“Well, then, where might the drugstore be?”
“I don’t know.”
“How about a good cheap hotel?”
“I don’t know.”
“Say, boy, you don’t know much, do you?”
“No, sir, I sure don’t. But I ain’t lost.””
—William Harmon (b. 1938)
“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)
“Fear, coercion, punishment, are the masculine remedies for moral weakness, but statistics show their failure for centuries. Why not change the system and try the education of the moral and intellectual faculties, cheerful surroundings, inspiring influences? Everything in our present system tends to lower the physical vitality, the self-respect, the moral tone, and to harden instead of reforming the criminal.”
—Elizabeth Cady Stanton (1815–1902)