For each admissible numbering, pick at least one pair of programs (but not necessarily all, which is impossible anyway) where the first translates from a given admissible numbering to that one, and the second work in the opposite way.

Now define a language consisting of all the pairs of programs chosen by one such way, for all admissible numberings. Is there such a language being recursively enumerable?

In other words, is there a way to enumerate all possible, sane programming languages (in the form of compilers), in a Turing-machine?

It is not even recognizable whether the two programs defines an admissible numbering. But it doesn't matter much since we only need to get one pair of translators for each numbering.

  • $\begingroup$ I don't understand how the final question relates to the into. By definition, given an admissible numbering, the language of pairs of programs which translate to each other is decidable. Perhaps you can try defining your question more formally? $\endgroup$
    – Ariel
    Commented Jul 12, 2017 at 8:49
  • $\begingroup$ @Ariel I think the first two paragraphs are formal enough. The final paragraph didn't actually add anything. As I'm aware, given an admissible numbering, the pair of programs which translates from and to it exists. Where does it say it is also decidable in some forms? $\endgroup$
    – user23013
    Commented Jul 12, 2017 at 9:07
  • $\begingroup$ It would help if you linked to a definition of admissible numbering, as there are several possible such notions. $\endgroup$ Commented Jul 13, 2017 at 7:40


Your Answer

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

Browse other questions tagged or ask your own question.