The Word Problem For Semi-Thue Systems
The word problem for semi-Thue systems can be stated as follows: Given a semi-Thue system and two words, can be transformed into by applying rules from ? This problem is undecidable, i.e. there is no general algorithm for solving this problem. This even holds if we limit the input to finite systems.
Martin Davis offers the lay reader a two-page proof in his article "What is a Computation?" pp. 258–259 with commentary p. 257. Davis casts the proof in this manner: "Invent whose solution would lead to a solution to the halting problem."
Read more about this topic: Semi-Thue System
Famous quotes containing the words word, problem and/or systems:
“What drivel it all is!... A string of words called religion. Another string of words called philosophy. Half a dozen other strings called political ideals. And all the words either ambiguous or meaningless. And people getting so excited about them they’ll murder their neighbours for using a word they don’t happen to like. A word that probably doesn’t mean as much as a good belch. Just a noise without even the excuse of gas on the stomach.”
—Aldous Huxley (1894–1963)
“... your problem is your role models were models.”
—Jane Wagner (b. 1935)
“What avails it that you are a Christian, if you are not purer than the heathen, if you deny yourself no more, if you are not more religious? I know of many systems of religion esteemed heathenish whose precepts fill the reader with shame, and provoke him to new endeavors, though it be to the performance of rites merely.”
—Henry David Thoreau (1817–1862)