1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – greybeard
    Apr 26, 2021 at 5:12
  • $\begingroup$ @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? $\endgroup$
    – RFV
    Apr 26, 2021 at 5:15

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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).

Improve this answer
$\endgroup$
6
  • $\begingroup$ code of a Turing Machine machine definition? transition function/table? $\endgroup$
    – greybeard
    Apr 26, 2021 at 6:04
  • $\begingroup$ This post should answer your question. $\endgroup$
    – Nathaniel
    Apr 26, 2021 at 6:12
  • $\begingroup$ If it is undecidable to know if two Turing machines have the same language, then how do programmer know that they have different algorithms for the same computable function, ie how do programmers know that one sort algorithms [one tm] is equivalent to another sort algorithm [another tm]. The knowledge that the programmer has, surely is used to reason about its equivalence, hence it self is a computation. What knowledge does an observer of algorithms or turing machines have that cannot be use to compute a solution? $\endgroup$
    – RFV
    Apr 26, 2021 at 6:44
  • $\begingroup$ The fact that it is undecidable means that there is no general method that works for any kind of algorithm. That does not contradict the that for certain particular algorithms, a particular method can work (but that particular method may not be usable for another algorithm). $\endgroup$
    – Nathaniel
    Apr 26, 2021 at 6:47
  • $\begingroup$ It should be impossible to enumerate all algorithms that match with an initial algorithm even for n=1, you would need to exclude all algorithms that don't halt but include a significant amount of algorithms that do halt, which is impossible. $\endgroup$
    – Albert Hendriks
    Apr 26, 2021 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.