Notes

Chapter 12: The Principle of Computational Equivalence

Section 8: Undecidability and Intractability


Undecidability in Mathematica

In choosing functions to build into Mathematica I tried to avoid ones that would often encounter undecidability. And this is why for example there is no built-in function in Mathematica that tries to predict whether a given program will terminate. But inevitably functions like FixedPoint, ReplaceRepeated and FullSimplify can run into undecidability—so that ultimately they have to be limited by constructs such as $IterationLimit and TimeConstraint.


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