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:
“The word “forbearance” is the key to a happy home.”
—Chinese proverb.
“The problem with marriage is that it ends every night after making love, and it must be rebuilt every morning before breakfast.”
—Gabriel García Márquez (b. 1928)
“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)