学到老Never too old to learn分享 http://blog.sciencenet.cn/u/tangchangjie

博文

中美学生思维差异、RSA蓝军以及盗梦算法争议与实验 精选

已有 11681 次阅读 2010-11-6 14:47 |个人分类:科普札记|系统分类:科普集锦| 悖论, 盗梦空间, 中美学生, 思维差异, RSA

中美学生思维差异、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页面)


 
 



https://wap.sciencenet.cn/blog-287179-380976.html

上一篇:递归梦的判定性与图灵停机问题--盗梦空间科普札记之三
下一篇:群星正灿烂,科学有希望
收藏 IP: 218.88.7.*| 热度|

21 张利华 罗岚 孟津 赫英 彭思龙 赵凤光 吉宗祥 杨正瓴 吕喆 侯成亚 鲍海飞 许培扬 刘广明 郑皎凌 董增寿 马磊 杨文祥 icgwang dulizhi95 ffy hxdai2008

该博文允许注册用户评论 请点击登录 评论 (12 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-10-5 23:27

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部