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:
“... the word “education” has an evil sound in politics; there is a pretense of education,
when the real purpose is coercion without the use of force.”
—Hannah Arendt (1906–1975)
“I don’t have any problem with a reporter or a news person who says the President is uninformed on this issue or that issue. I don’t think any of us would challenge that. I do have a problem with the singular focus on this, as if that’s the only standard by which we ought to judge a president. What we learned in the last administration was how little having an encyclopedic grasp of all the facts has to do with governing.”
—David R. Gergen (b. 1942)
“People stress the violence. That’s the smallest part of it. Football is brutal only from a distance. In the middle of it there’s a calm, a tranquility. The players accept pain. There’s a sense of order even at the end of a running play with bodies stewn everywhere. When the systems interlock, there’s a satisfaction to the game that can’t be duplicated. There’s a harmony.”
—Don Delillo (b. 1926)