Notes

Chapter 12: The Principle of Computational Equivalence

Section 8: Undecidability and Intractability


Sequence equations

One can ask whether by replacing variables by sequences one can satisfy so-called word or string equations such as

Flatten[{x,0,x,0,y}] == Flatten[{y,x,0,y,1,0,1,0,0}]

(with shortest solution x={1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0}, y={1, 0, 1, 0, 0, 1, 0, 1, 0, 0}). Knowing about PCP and Diophantine equations one might expect that in general this would be undecidable. But in 1977 Gennadií Makanin gave a complicated algorithm that solves the problem completely in a finite number of steps (though in general triple exponential in the length of the equation).


From Stephen Wolfram: A New Kind of Science [citation]