|||
中美学生思维差异、RSA蓝军以及盗梦算法争议与实验
----盗梦空间科普札记之四
1中美学生思维方式差异
曾见过一文,议论中美学生思维方式差异,说:在某国际学生夏令营,数学老师出一个题目:“一昼夜中时钟的上的分针和时针重合多少次?”
中国学生善逻辑思维,立即拿笔画图计算;美国学生善观察,取下手表拨针做实验;因为其中还有一点思维转弯,如果规定时间比较短,两种方法都可能出错,但从统计的角度看,美国学生的实验法出错率会少一些。
我更喜欢两种方法的结合,先观察自然现象或实验结果,然后上升到理论解释。一般非纯理论的科学家做研究都不会拒绝这种方法,就是理论性很强的科学问题,例如相对论理论研究,也要做思想实验、也要用观察去验证理论。
2 深思者提出的问题
言归正传,回到 关于盗梦空间的科普话题。
上篇博文 递归梦的判定性与图灵停机问题--盗梦空间科普札记之三 引起了讨论.上篇博文主要结论是:
命题 递归梦是不可判定的,即不可能设计这样一个通用程序P,它能检查一切的梦串对<M,s>对应的那个梦是否会醒过来。
博友的讨论很深入、认真。 一些深思者提出了比较深刻、比较难回答的问题。例如。上篇博文的第8条评论给出了质疑,大致要点包括:
(1) 证明感觉像是悖论 ; (2)是否具有实际意义?(3) 唐文的程序A1看起不像递归, 评论者自己还给出了一段自称是“无聊”的程序A2(如下),说与A1等效:
bool M ( s) { ... bool OK = !(M(s); ....; return OK;} }
要求分析是否悖论或其意义,还单独发了博文,详请可 点击这里 。
想不到几篇娱乐兼科普的博文引出了许多内行来讨论,分析这些问题出现的原因,大致有:
(a)问题的确比较搅人;
(b)笔者解释得还不够细致、不够通俗。
虽在回复中做了一些简答,还不够满意;因为,每年这一堂课后,都有类似的问题;这些问题有一定深度和难度,非深思者提不出来,不深思也回答不了。
怎样改进这一部分课程的教学呢?思考正纠结,这个问题被博友的实验解决了。
3 实践是检验科普博文的方法之一
今天,博友liuhuimin 在上文的讨论区发了评论(第13条),给出了试验程序,这里稍改排版格式,括号中的注释是本博主加的。他们的实验一方面回答了第8条评论给出的质疑,说明可能有误解或理解偏差。重要的是,提供了一个好例子。以后讲课到这部分、出现类似问题时,就可用这个例子。liuhuimin 的评论(上篇博文 第13条)如下:
我们兴趣小组热烈讨论了8楼的问题,开始(表决)是3:3;后来做了实验,在VC 6中写了程序做实验验证,果然,如唐老师说的两种结果。两个程序和运行结果如下:
(a)无递归深度控制时:
bool test_dream( )
{ printf("检查盗梦空间递归程序rn");
test_dream( );
return true;
}
运行结果 ,用VC6中跟踪工具,可以看到 出错消息:
Unhandled exception in Test (MSVCRTD.DLL):OXC0000FD:scak Overflow
出现了栈溢出。
博主注:博主重复了这个试验,在Win7上等比较稳定的系统,系统能处理exception,只死去程序本身(而不会死机);程序是错的,不能正确运行;当然也就不会推出上文评论8所谓的悖论了。
(b) 有递归深度控制的如下:
bool test_dream2(int N) //有递归(深度)控制
{ bool results=true;
if (N==0) return true;
else N--;
printf("检查盗梦空间递归程序rn");
results= !( test_dream2(N));
return results;
}
运行结果:
N=偶数 结果为 True;
N=奇数 结果为 false.
不会推出矛盾,也不会推出悖论。
博主注:笔者重复了这个试验,程序能正常,但是,会按递归的层次数量的奇偶性给出确定的结果,没有出现质疑者设想的悖论。两个程序合起来,说明那个自称“无聊”的算法A2, 不等价于博主给出的算法A1。
这些讨论回答了那一个关于“递归梦是不可判定的” 质疑。
有兴趣的内行,如果想看细致的讨论,可参考上篇博文及其评论之8---11等条目,其中,凝聚着博友们的深思。
这个兴趣小组先做实验、观察事实,再用理论用模型去解释事实的方法特别可嘉。说明他们的在研究方法上已经上路,而导师招生时,可能都会喜欢这样的学生。
4 RSA算法研究过程中的蓝军
就像论证三峡工程一样,质疑者扮演蓝军,提出了可能的问题,把可能的问题都考虑了,工程就可靠了。 在这一意义上,质疑者都是贡献者。
在RSA公钥加密算法研制过程中,Ron Rivest、Adi Shamirh 扮演红军,负责防卫;Lenonad Adleman扮演蓝军,负责发攻击和破解;RSA目前仍然最有影响力的公钥加密算法,能够抵抗到目前为止已知的所有密码攻击,RSA取名来自开他们三位研究者的名字,而Adleman扮演蓝军之功不可没。
其实,对上面博文讨论的问题,笔者以前的认识还不是很深刻,通过这次回答和程序实验,理解也加深、感谢质疑,欢迎继续质疑。
在这个义上,实践是检验真理的标准,也是检验科普博文的标准。
参考文献
[1] Material: Sipser, Michael (@MIT), Introduction to the Theory of Computation. PWS Publishing Company, 1997 ,机械工业出版社出版,2002。
[2]) Michael Sipser (麻省理工学院),计算理论导引(第二版), 中译本 ,唐常杰 陈鹏 向勇 刘齐宏 译,机械工业出版社出版,2006.7
相关博文:
盗梦空间科普札记之一:梦里乾坤递归深,醒来可知在哪层?
盗梦空间科普札记之四: 中美学生思维差异、RSA蓝军以及盗梦算法争议与实验
可计算理论是门修养课-研教散记11 (去年的博文);
知识的共创和共享-研教散记(4) 可在出版社网址下载课程的PPT,1600页面)
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-10-5 23:27
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社