[Haskell-cafe] Re : Friedberg numberings
Pierre-Etienne Meunier
pierreetienne.meunier at gmail.com
Thu Feb 18 08:17:48 EST 2010
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...
More information about the Haskell-Cafe
mailing list