History and Importance
Semi-Thue systems were developed as part of a program to add additional constructs to logic, so as to create systems such as propositional logic, that would allow general mathematical theorems to be expressed in a formal language, and then proven and verified in an automatic, mechanical fashion. The hope was that the act of theorem proving could then be reduced to a set of defined manipulations on a set of strings. It was subsequently realized that semi-Thue systems are isomorphic to unrestricted grammars, which in turn are known to be isomorphic to Turing machines. This method of research succeeded and now computers can be used to verify the proofs of mathematic and logical theorems.
At the suggestion of Alonzo Church, Emil Post in a paper published in 1947, first proved "a certain Problem of Thue" to be unsolvable, what Martin Davis states as "...the first unsolvability proof for a problem from classical mathematics -- in this case the word problem for semigroups." (Undecidable p. 292)
Davis asserts that the proof was offered independently by A. A. Markov (C. R. (Doklady) Acad. Sci. U.S.S.R. (n.s.) 55(1947), pp. 583–586.
Read more about this topic: Semi-Thue System
Famous quotes containing the words history and, history and/or importance:
“The principle that human nature, in its psychological aspects, is nothing more than a product of history and given social relations removes all barriers to coercion and manipulation by the powerful.”
—Noam Chomsky (b. 1928)
“History takes time.... History makes memory.”
—Gertrude Stein (1874–1946)
“The importance of a lost romantic vision should not be underestimated. In such a vision is power as well as joy. In it is meaning. Life is flat, barren, zestless, if one can find one’s lost vision nowhere.”
—Sarah Patton Boyle, U.S. civil rights activist and author. The Desegregated Heart, part 1, ch. 19 (1962)