18 Feb
2010
18 Feb
'10
1:17 p.m.
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...
6023
Age (days ago)
6023
Last active (days ago)
0 comments
1 participants
participants (1)
-
Pierre-Etienne Meunier