我們可以決定一個數n是否屬於一個可數集S？

Question

現在的問題如下：

設S是N（自然數）的一個子集，所以它是無限且可數的。讓Ls = {a^n | n屬於一種語言。是遞歸的？ Ls是遞歸枚舉？證明你的答案。

我很確定Ls對任何S都是遞歸的，因爲我們可以編寫一個決定Ls（或者Turing Machine）的程序。但我如何證明它呢？

Answer 1

不，你不能。在字符串和數字之間有簡單的，可計算的同構（例如，對於大小爲n的字母表，將字符串作爲基數n中的數字加上一些化妝品用於前導零）。所以如果所有的數字集合都是可判定的或可枚舉的，那麼所有的字符串集合都是如此。