complexity-theory - 计算复杂性：对大多数决策问题无法计算的证明中的矛盾感到困惑

Question

我对这个证明有点困惑，这个证明是在这个讲座的 13 分钟时给出的： https ://www.youtube.com/watch?v=moPtwq_cVH8

证明依赖于程序必须是有限的这一事实，使得所有程序的集合小于所有函数的集合。这应该意味着存在一个理论上最大大小的程序，因为假设所有程序 S 的集合，它声称是有限的，其大小为 N。现在，如果我们取 N 中最大的程序，并添加 1 位，我们现在创建了一个不在 S 中的程序，这与 S 是所有程序的集合的陈述相矛盾。

但是对于任意大小 K 的任何程序，您都可以制作一个大小为 K+1 的程序。这意味着不能有最大尺寸程序。

标签： complexity-theory

Answer 1

你误会了。每个程序都是有限的。不是程序集。