Has “computational equivalence” got an official definition I can cite from a book somewhere or other?
I pulled out of my ahem hat the following:
For two systems to be computationally equivalent, it must be that for each X in the domain of the computation they are supposed to execute, and for each Y = f(X), (where f(X) is the function corresponding to that computation,) both systems, when beginning from a state that represents X, transform into a state that represents Y.
But I was basically making this up, hopefully based on memories of what the concept actually means to people who use it.
Am I basically right? Whether I am or not, where can I find something to quote rather than just this blurb I’ve made up as a summary of my own understanding of the concept?
Please don’t tell me that what computational equivalence amounts to is controversial. Unless it’s true I guess.
I can certainly think of one example, Fourier transforms, where there is the hard way to compute em, and the much easier way (computational wise), but in the end you get the exact same answer either way. I can’t imagine, nor have I heard of anything controversial regarding those. Though I await the local SDMB Fourier expert to at least mildy correct said statements
I’ve never heard the term “computational equivalence”, but for the idea you’re trying to capture, I’d word it something like this:
In the case where S and T have no internal state, it’s sufficient to consider input sequences of length one, but otherwise you need to be sure that they aren’t agreeing on the first k items and then diverging afterwards.
Wolfram does use the term in a somewhat ideosyncratic way though, I believe.
Intuitively, I would consider computational equivalence to mean Turing equivalence, in which case I believe that the definition is: Two systems S and T are Turing equivalent if S is Turing reducible to T and T is Turing reducible to S; a system A is Turing reducible to a system B if, given an oracle for B (intuitively, a sort of list of outputs of B), every element of A can be computed.
I think this differs from the definition in the OP somewhat – for instance, I would consider systems to be computationally equivalent even if they give different outputs for the same inputs, provided there is some means of ‘translating’ between the two. If, for instance, S(x) != T(x) for general x, but there always exists some p such that S(px) = T(x). Intuitively, this corresponds to the notion of S being able to do the same computations as T, even though it might need a different program to do so.
