Notes

Chapter 12: The Principle of Computational Equivalence

Section 6: Computational Irreducibility


Speed-up theorems

That there exist computations that are arbitrarily computationally reducible was noted in work on the theory of computation in the mid-1960s.


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