不属于递归可枚举集的超过 {0, 1} 的一组语言是不可数的

Question

我有一个计算理论的问题，即

证明

A set of languages over an alphabet Σ = {0, 1} which does not belong to Recursively Enumerable set, are uncountable.

谁能简单解释一下？

Answer 1

首先请注意，字母表 {0,1} 上的整个语言集已经不可数，因为它可以与 0 和 1 之间的实数 1-1 对应。

要看到这一点，请使用以下构造将二进制表示的 0 和 1 之间的实数与一个集合相关联。 （为了演示目的，我使用了有限实数）：

0.00111 -> {“0”、“01”、“001”、“0011”、“00111”、“001110”、“0011100”、...}

因此，对于 [0,1) 范围内的每个实数，都有一个包含每个长度的字符串的唯一对应语言。

好吧，这对于超过 {0,1} 的整个语言集来说都很好，但是非 R.E 的语言呢？语言？足以证明集合或R.E。语言是可数的。如R.E。语言是可数的，其余的语言一定是非R.E。语言，而且这些语言必须是不可数的。

为了解决这个问题，知道图灵机集是可数的就足够了。我们将用一个有限字符串来描述每个图灵机，显示其状态、转换函数等。最后，请注意每个 R.E。语言可由图灵机计算，因此 R.E。因此语言必须是可数的。