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).



Image Source Notebooks:

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