Computational Equivalence and Classical Recursion Theory

Two central results in Wolfram’s A New Kind of Science [17] have attracted close scrutiny by the computability theory community: the first is the computational universality of elementary cellular automaton rule number 110, the other the Principle of Computational Equivalence, see section 2 below.