# Given an algorithm, is it possible to find all other equivalent algorithms for the same computable function in the same model

For any computable-function, there may be multiple different algorithms (possibly countably infinite). For example, sort has many different implementations/algorithms, that we know of or that we have found so far. They all produce the same output for the same input.

Given any specific computable-function or even a specific instance of an algorithm/implementation (for any model of computation, functional in lambda calculus, imperative in turing machines, or any other) for it, is it possible to enumerate/find all other equivalent algorithms/implementations for that same computable-function, for the same model.

ie. If I have an algorithm or even a specification for sort, it is possible to find the other algorithms for sort?

• For implementations, the answer for serial execution got to be you'll never finish enumerating them all for any model allowing an operation to be inverted. Apr 26 at 5:12
• @greybeard Since there may be possible countably infinite number of implementations, that would make sence, but is ti possible to find ANY other implementations? If I have bubble sort, can I find quick sort?
– RFV
Apr 26 at 5:15

Interpreting your problem as finding a computable $$f$$ such that $$f\big(\langle M\rangle\big)=\langle M'\rangle$$ with the property that $$M'$$ enumerates all programs equivalent to $$M$$, i.e. all $$M''$$ with $$L(M'')=L(M)$$, the answer is no (such $$f$$ does not exist).

One way to show this is to observe that such $$f$$ would place the language $$\left\{\big(\langle M_1\rangle, \langle M_2\rangle\big) \big| \; L(M_1)=L(M_2)\right\}$$ in $$RE$$, while it is known that this language is $$\Pi_2$$ complete and thus not in $$RE$$. You could formulate this relative to any admissible numbering, and not necessarily in the language of Turing machines.

You should think in Turing Machines.

If I understand correctly, what you ask is more or less "Given the code of a Turing Machine, is it possible to enumerate the codes of all Turing Machines with the same language?".

I think this is not possible, because it is undecidable to know whether two TM have the same languages (all the more so list all TM with the same language).

• code of a Turing Machine machine definition? transition function/table? Apr 26 at 6:04