[Haskell-cafe] Re : Friedberg numberings

[Pierre-Etienne Meunier]

Hi,

In fact it is not quite hard to see that such a numbering exists : just take any numbering of all Turing machines, say {\phi_i}, then remove all indices i such that there is j<i such that \phi_j = \phi_i (equality is mathematically correctly defined between functions from N to N).

Ah, and also, notice that what you call a "programming language" is nothing else than an enumeration of all Turing machines.

However, if by "construction" you meant "recursive construction", i.e. for another enumeration (\psi_i), find a Turing machine computing for any i, the index j such that \phi_j=\psi_i, then it is clear that it is not possible : it would allow to decide the equality problem for Turing machines.

Hope this helps...