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 the word, word, problem and/or systems:
“Please stop using the word “Negro.”... We are the only human beings in the world with fifty-seven variety of complexions who are classed together as a single racial unit. Therefore, we are really truly colored people, and that is the only name in the English language which accurately describes us.”
—Mary Church Terrell (1863–1954)
“Tax avoidance means that you hire a $250,000-fee lawyer, and he changes the word ‘evasion’ into the word ‘avoidance.’”
—Franklin D. Roosevelt (1882–1945)
“The general public is easy. You don’t have to answer to anyone; and as long as you follow the rules of your profession, you needn’t worry about the consequences. But the problem with the powerful and rich is that when they are sick, they really want their doctors to cure them.”
—Molière [Jean Baptiste Poquelin] (1622–1673)
“I am beginning to suspect all elaborate and special systems of education. They seem to me to be built up on the supposition that every child is a kind of idiot who must be taught to think.”
—Anne Sullivan (1866–1936)