我们可以决定一个数n是否属于一个可数集S？

Question

现在的问题如下：

设S是N（自然数）的一个子集，所以它是无限且可数的。让Ls = {a^n | n属于一种语言。是递归的？ Ls是递归枚举？证明你的答案。

我很确定Ls对任何S都是递归的，因为我们可以编写一个决定Ls（或者Turing Machine）的程序。但我如何证明它呢？

Answer 1

不，你不能。在字符串和数字之间有简单的，可计算的同构（例如，对于大小为n的字母表，将字符串作为基数n中的数字加上一些化妆品用于前导零）。所以如果所有的数字集合都是可判定的或可枚举的，那么所有的字符串集合都是如此。