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
    Jul 12 '17 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
    Jul 12 '17 at 9:07
  • $\begingroup$ It would help if you linked to a definition of admissible numbering, as there are several possible such notions. $\endgroup$ Jul 13 '17 at 7:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.