为什么缺乏对电源集的陈述不足以证明存在不可决定的语言？

Question

从这个说法

由于$ mathbb {n} $没有报明$ m m iathcal {p}（ m athbb {n}）$，因此必须存在一种不可否认的语言。

我想理解为什么类似的推理不适合 有限 设置$ b $，也没有对$ Mathcal {p}（b）$的污垢！ （带有$ | b | = k $和$ k in mathbb {n} $）

为什么无限套件的最低需求？

编辑注意：

尽管我选择了答案，但许多答案 和所有评论 是重要的。

Answer 1

如果您采用任何有限的TM $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $ a $，而有限的powerset则足以满足。但这不是我们想要的。我们想证明有一种不可决定的语言，即一种语言 不 TM可以决定。有限套件与其功率集之间的基数差异不会表明这一点。您需要与所有TM的集合的基数差异，这是可以算出的，可以说有一种语言不是由集合中的任何机器决定的。

Answer 2

让我们首先概括在哪种情况下引用的陈述有意义。

1. 让我们将自己限制在$ mathbb {n} to {0,1 } $中（所有函数的子集）中的（决策）函数的域。
2. 每个这样的功能都对应$ mathcal {p}的一个元素（ mathbb {n}）$（请参阅 特征功能).
3. 有很多图灵机（简单编码）都有很多。

到1.和2.，有很多功能。因此，有一些功能没有相应的图灵机，也就是说它们是不可计算的。很简单 太多 功能;这就是“没有污染”的含义。

现在，$ mathcal {p}（ mathbb {n}）$中只有许多有限集 康托的配对功能）。因此，仅考虑有限集时，不能得出相同的矛盾。

如果您在基础设置中添加一些无限的集合，以使其变得不可数，那么没有理由相信某些有限的集合是不可决定的。你只知道那里 是 一些不确定的集合。实际上， 所有有限套件都是可决定的, ，因此罪魁祸首始终是无限集。