Two Years of Struggle with Computational Equivalence
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.
(April 20, 2004)