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:
“Even the most honest writer lets slip a word too many when he wants to round off a period.”
—Friedrich Nietzsche (1844–1900)
“[How] the young . . . can grow from the primitive to the civilized, from emotional anarchy to the disciplined freedom of maturity without losing the joy of spontaneity and the peace of self-honesty is a problem of education that no school and no culture have ever solved.”
—Leontine Young (20th century)
“Our little systems have their day;
They have their day and cease to be:
They are but broken lights of thee,
And thou, O Lord, art more than they.”
—Alfred Tennyson (1809–1892)