computation-theory - 我们能否判断一个数 n 是否属于可数集 S？

Question

手头的问题如下：

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

我很确定 Ls 对于任何 S 都是递归的，因为我们可以编写一个决定 Ls 的程序（或就此而言的图灵机）。但是我该如何证明呢？

Answer 1

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