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/or importance:
“In history as in human life, regret does not bring back a lost moment and a thousand years will not recover something lost in a single hour.”
—Stefan Zweig (18811942)
“I am not sure that it is of the first importance that you should be happy. Many an unhappy man has been of deep service to himself and to the world.”
—Woodrow Wilson (1856–1924)