11

一些程序员在理论 CS 课程中看不到太多相关性(尤其是我的学生)。这是我觉得非常相关的事情。让我为那些以前没有看过它的人构建它......

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

B) 图灵机识别语言。

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

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

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

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

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

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

我的问题差不多到了……

每当我向学生提出这个论点时,他们都会陷入可数与不可数无限之间。他们通常没有很强的数学背景,所以试图通过康托尔的对角化论证来解释往往会让他们眼花缭乱。

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

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

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

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

4

9 回答 9

6

我推荐的向数学背景有限的人教授无穷级的第一步是“为什么数学家说偶数集和整数集大小相同?” 这引入了“如果您可以将集合 A 的每个成员与集合 B 的一个成员相关联,那么数学家会说这些集合具有相同的大小。” 接下来显示每个分数(每个有理数)都可以使用对角线方法与一个计数数相关联。一旦他们满意了,我就提出π,大家都知道它的十进制表达式中有无限个不重复的数字,这意味着它不能表示为分数,所以它会被留下来,这意味着无理数集大于计数数集。π,但你可以用“好的,聪明的,以 π 为底数写下一周中的天数”来回答他们。

于 2009-06-16T01:53:21.100 回答
3

“非常相关”的部分在哪里?

编辑:好的,我已经专业编写代码 13 年了,我不会调用与我做过的任何事情相关的无穷大级别。

我想我会从你的理论中得出不同的结论。“我们只能解决所有问题中的极小部分”是我们工艺的极限吗?

在我看来,有无数个问题(可数或不可数似乎没有区别)。因此,我们的手艺是无限的——我们永远不会用完要解决的问题。

于 2009-06-16T00:54:20.897 回答
2

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

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

我认为连续统的基数原则也很有帮助,尽管也许可以简化到初学者的水平。表明除了简单的实数与整数之外还有更多可能有助于“点击”。

于 2009-06-16T00:52:53.693 回答
2

英语中有数以万计的单词。您可以计算一本书中的单词数或宇宙中的书数。你无法计算将要出版的书的数量

于 2009-06-16T01:12:18.280 回答
1

原谅下面写得不好的隐喻。

我个人认为可数/不可数二分法与芝诺的箭悖论密切相关。

所有自然数的集合都是可数的,有一种生成“下一个”整数的特定方法,它会让你向前迈出一步。从这个意义上说,可数集是向前移动的。就好像它有一个速度,它一直在前进。


所有实数的集合是不可数的,就像芝诺的箭头一样。

如果您必须在起点 (0) 和终点 (1 == 2 -0 ) 之间移动,则必须先通过中点 (1/2 == 2 -1 )。

现在你的目的地是 1/2;如果您必须在原点 (0) 和 (1/2) 之间移动,则必须通过中点 (1/4 == 2 -2 )

以此类推,所以要在 0 和 1 之间,你必须首先在中间的东西之间,你必须首先在中间的东西之间。没有计算“下一步”的有限方法,所以速度(与自然数的速度相反)并不真正存在,你的下一步不会带你去任何地方。

编辑:

我现在意识到这可能与自然数集到任何可数集的总排序和映射有关。 如果您不能完全订购一组中的项目,或者您无法创建一种方法来确定一组中的下一个项目是什么,那么它很可能是不可数的。

于 2009-06-16T00:50:03.593 回答
1

G) 因此,如果一种语言是无限的,它就有无数个子集。这些中的每一个都代表一个问题。

需要引用。您不能仅仅假设任何(可能是无限的)图灵机集合必然代表一个独特的“问题”。至少,您必须(单独)将“问题”的定义形式化,就像图灵机已经形式化一样。

于 2009-06-16T06:59:46.933 回答
0

程序员(或者至少是我自己)通常不必以这种方式担心无穷大。当您在机器可表示的实数线的任何部分上放置一个有限框时,您将获得有限数量的实数。=)

例如,双精度变量具有有限数量的可能值:2^64。

于 2009-06-16T01:04:11.420 回答
0

下面是一个可计算问题的例子:在国际象棋比赛开始时,白棋有可能强行获胜吗?

可能的移动和反移动的数量是有限的。我们所要做的就是建造树木并修剪它们。我们还没有这样做,只是因为使用当前的技术需要数十亿年的时间。

这是一个不可计算的问题示例:给定一个场景的二维视图,构建场景的完整三维模型。

我们一直这样做。(做一个门上有窥视孔的房间。找人装修。从洞里看,描述你看到的一切。)

我们不计算不可计算的。我们产生一个近似结果(就像我们计算和使用一个近似值 pi,另一个无法计算的数字)。随着更多信息的出现,我们会不断更新结果。这就是视错觉的全部内容。当你看“一个花瓶,还是两张脸”的图片时 你的视觉系统说“这是一个花瓶。不。等等。这是两张脸。不。等等。这是一个花瓶。” 您会看到它在两种解释之间来回切换。

仅仅因为某事不可计算,就没有理由不去做。

于 2009-06-16T02:19:33.503 回答
-5

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

你必须是网页设计师。

于 2009-06-16T01:28:09.927 回答