The Word Problem in Combinatorial Calculus
The simplest example of an undecidable word problem occurs in combinatory logic: when are two strings of combinators equivalent? Because combinators encode all possible Turing machines, and the equivalence of two Turing machines is undecidable, it follows that the equivalence of two strings of combinators is undecidable.
Likewise, one has essentially the same problem in lambda calculus: given two distinct lambda expressions, there is no algorithm which can discern whether they are equivalent or not; equivalence is undecidable.
Read more about this topic: Word Problem (mathematics)
Famous quotes containing the words word, problem and/or calculus:
“Of the modes of persuasion furnished by the spoken word there are three kinds. The first kind depends on the personal character of the speaker; the second on putting the audience into a certain frame of mind; the third on the proof, provided by the words of the speech itself.”
—Aristotle (384–323 B.C.)
“[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)
“I try to make a rough music, a dance of the mind, a calculus of the emotions, a driving beat of praise out of the pain and mystery that surround me and become me. My poems are meant to make your mind get up and shout.”
—Judith Johnson Sherwin (b. 1936)