turing-machines - 多个级别的无穷大

Question

关闭。这个问题是off-topic .它目前不接受答案。












想改善这个问题吗？ Update the question所以它是 on-topic对于堆栈溢出。

12 年前关闭。




Improve this question




一些程序员在理论 CS 类(class)中没有看到太多相关性(尤其是我的学生)。这是我认为非常相关的事情。让我为那些以前没有见过它的人把它分成几部分......

A) 编程问题可以改写为关于语言的问题。

B) 图灵机识别语言。

C)图灵机可以编码为(大)整数。

D)因此，可能的图灵机的数量是可数无限的

E)一个集合的幂集就是这个集合的所有可能的子集。

F) 如果一个集合是可数无限的，它的幂集就更大，即不可数无限。

G) 因此，如果一种语言是无限的，则它具有不可数的无限数量的子集。每一个都代表一个问题。但是可以解决这些问题的图灵机数量有限。如果我们不能用图灵机解决一个问题，它就无法解决。

结论......我们只能解决所有问题中的一小部分。

我的问题几乎在这里......

每当我向学生提出这个论点时，他们都会陷入可数与不可数无限的问题上。他们通常没有很强的数学背景，所以试图通过康托尔的对角化论证来解释往往会让他们目瞪口呆。

通常我会尝试给他们一些他们可以掌握的东西，就像这样......在计数线的任何部分放置一个有限框，我们捕获这些数字的有限数量......但是在任何部分放置一个有限框实数轴，我们捕获了无限数量的实数。一种证明实数比计数数多的证据。

最后我的问题......你如何向那些从未听说过这个概念并且可能没有数学倾向的人解释多级无穷大的概念？

最终编辑:通过问这个问题我学到了很多东西，我很感激反馈。我浪费了太多时间试图弄清楚“社区维基”究竟是什么。我了解到有些人对理论问题存在固有的偏见，我认为这只是一个错误，因为我们今天所做的很多事情都是昨天的理论。但这种偏见是很自然的，虽然我不同意他们对理论的值(value)，但我对此没有异议，它帮助我了解我的学生来自哪里。我确实认为 BS 评论是不必要的。

我觉得这个问题根本不是民意调查或 2009 年的预测问题。那些只想要带有编码答案的编码问题的人可能想要重新检查该要求。我已将此问题移至社区维基，但强烈认为我是由于不当使用武力而被迫这样做的。

Answer 1

我认为你的解释是最简单的，因为这是我学到的。这几乎就像实数有无穷多个维度。它在一个方向上是无限的，但在另一个方向上也是无限的。

对角化是一个非常酷的实验，但我可以看到它如何超越初学者的头脑。但是，如果它以非常刻意的方式进行展示，并且进展非常缓慢，那么它确实是有道理的。我想，只是快速抛出数字可能很难理解。

我认为Cardinality of the Continuum的原理也很有帮助，尽管也许可以简化为初学者级别。表明除了简单的实数与整数之外还有更多内容可以潜在地帮助“点击”。