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