一些程序员在理论 CS 课程中看不到太多相关性(尤其是我的学生)。这是我觉得非常相关的事情。让我为那些以前没有看过它的人构建它......
A) 编程问题可以改写为关于语言的问题。
B) 图灵机识别语言。
C)图灵机可以编码为(大)整数。
D)因此,可能的图灵机的数量是可数无限的
E) 一个集合的幂集就是该集合的所有可能子集。
F) 如果一个集合是可数无限的,它的幂集更大,即不可数无限。
G) 因此,如果一种语言是无限的,它就有无数个子集。这些中的每一个都代表一个问题。但是只有无数的图灵机可以用来解决这些问题。如果我们不能用图灵机解决问题,它就无法解决。
结论……我们只能解决所有问题的一小部分。
我的问题差不多到了……
每当我向学生提出这个论点时,他们都会陷入可数与不可数无限之间。他们通常没有很强的数学背景,所以试图通过康托尔的对角化论证来解释往往会让他们眼花缭乱。
通常我会尝试给他们一些他们可以掌握的东西,就像这样......在计数线的任何部分放置一个有限的盒子,我们捕获这些数字的有限数量......但是在任何部分放置一个有限的盒子实数线,我们捕获了无限数量的实数。一种证明实数比计数数多的证据。
最后我的问题......你如何向那些从未听说过这个概念并且可能没有数学倾向的人解释多重无穷大的概念?
最终编辑:通过提出这个问题,我学到了很多东西,我很感激反馈。我浪费了太多时间试图弄清楚“社区维基”到底是什么。我了解到,有些人对理论问题存在固有的偏见,我认为这只是一个错误,因为我们今天所做的很多事情都是昨天的理论。但是这种偏见是很自然的,虽然我不同意他们对理论价值的看法,但我对此没有异议,它有助于我了解我的学生来自哪里。我确实认为 BS 的评论是不必要的。
我根本不认为这个问题是民意调查或预测 2009 年的问题。那些只想要编码问题和编码答案的人可能想要重新检查该要求。我已将此问题移至社区 wiki,但强烈认为我因不当使用武力而被迫这样做。