# Definition of Computational Equivalence **URL:** \ **Category:** Factual Questions\ **Created:** [July 28, 2010, 6:26pm UTC](https://boards.straightdope.com/t/definition-of-computational-equivalence/548342 "2010-07-28T18:26:29Z")\ **Posts on this page:** 6\ **Page:** 1
**Author:** ![Frylock](https://avatars.discourse-cdn.com/v4/letter/f/ce7236/32.png) [@Frylock](https://boards.straightdope.com/u/Frylock)\ **Post date:** [July 28, 2010, 6:26pm UTC](https://boards.straightdope.com/t/definition-of-computational-equivalence/548342/1 "2010-07-28T18:26:29Z")
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. ---
**Author:** ![billfish678](https://avatars.discourse-cdn.com/v4/letter/b/7bcc69/32.png) [@billfish678](https://boards.straightdope.com/u/billfish678)\ **Post date:** [July 28, 2010, 6:46pm UTC](https://boards.straightdope.com/t/definition-of-computational-equivalence/548342/2 "2010-07-28T18:46:06Z")
Sounds decent to me. 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 🙂 ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 28, 2010, 6:46pm UTC](https://boards.straightdope.com/t/definition-of-computational-equivalence/548342/3 "2010-07-28T18:46:29Z")
I’ve never heard the term “computational equivalence”, but for the idea you’re trying to capture, I’d word it something like this: > [@](#): > > Two systems S and T are computationally equivalent iff for any finite sequence of inputs (x\_1, x\_2, …, x\_n), the sequences (S(x\_1), S(x\_2), …, S(x\_n)) and (T(x\_1), T(x\_2), …, T(x\_n)) are equal. 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. ---
**Author:** ![CookingWithGas](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/cookingwithgas/32/485_2.png) [@CookingWithGas](https://boards.straightdope.com/u/CookingWithGas)\ **Post date:** [July 28, 2010, 7:20pm UTC](https://boards.straightdope.com/t/definition-of-computational-equivalence/548342/4 "2010-07-28T19:20:33Z")
I haven’t figured out what this is all about but here is the stuff right from the guy who coined the term. > **[The Principle of Computational Equivalence: A New Kind of Science | Online by...](https://www.wolframscience.com/nks/chap-12--the-principle-of-computational-equivalence/)** > > List of all sections in Chapter 12 from Stephen Wolfram's A New Kind of Science ---
**Author:** ![Half\_Man\_Half\_Wit](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/half_man_half_wit/32/21766_2.png) [@Half\_Man\_Half\_Wit](https://boards.straightdope.com/u/Half_Man_Half_Wit)\ **Post date:** [July 28, 2010, 8:06pm UTC](https://boards.straightdope.com/t/definition-of-computational-equivalence/548342/5 "2010-07-28T20:06:49Z")
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. ---
**Author:** ![ultrafilter](https://avatars.discourse-cdn.com/v4/letter/u/3d9bf3/32.png) [@ultrafilter](https://boards.straightdope.com/u/ultrafilter)\ **Post date:** [July 28, 2010, 9:02pm UTC](https://boards.straightdope.com/t/definition-of-computational-equivalence/548342/6 "2010-07-28T21:02:35Z")
That’s a good point. So I’ll modify my definition to the following: > [@](#): > > Let S and T have mutual domain X, and respective codomains Y\_S and Y\_T. S and T are computationally equivalent iff there is a bijection f: Y\_T -\> Y\_S such that for any finite sequence of inputs (x\_1, x\_2, …, x\_n) drawn from X, the sequences (S(x\_1), S(x\_2), …, S(x\_n)) and (f(T(x\_1)), f(T(x\_2)), …, f(T(x\_n))) are equal. This way, we allow for different encodings, but we still have the possibility that S and T have internal state.