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.