Two Years of Struggle with Computational Equivalence

Matthew Frank
University of Chicago

What must a computation be in order for the principle of computational equivalence to hold? Two years of struggle with and correspondence on this question have left me with no clear answer about computational equivalence, but several insights about the peculiarities of the NKS notions of computation versus notions more familiar in mathematics. I present some of these insights, along with a more successful outcome to a briefer struggle with the principle of computational irreducibility.

Created by Mathematica  (April 20, 2004)