盗梦空间科普札记之三： 递归梦的判定性与图灵停机问题
　　
      上文 盗梦空间科普札记之二：用科学家的目光看《盗梦空间》 议论了思想植入问题。本文试图通俗地描述盗梦空间中的江湖险恶，想说明“递归梦是否停止”这一问题是不可判定的，设计中稍有不慎（如上篇博文第25条评论指出的Bug，附录中的C语言程序没有考虑边界条件），递归梦就是不归路。
    为了区别现实与电影，先考察：
1 递归梦与连续梦  
    人真的会做嵌套梦吗？ 在上篇博文的评论第20条，游客xuesnow 给出了自己的体验：“如果自己在梦中梦到自己醒了，而且醒了两次。就是醒来一次，其实还在梦里，再醒来了一次，还是在梦里。最后醒来，头痛，看到了现实的世界。这是不是N=3的情况？”
     问了一下，好多人都有过类似体验，大多发生在睡得不太深沉时，例如夏天午睡，或紧张思索科学问题不得其解时，迷迷糊糊，好像醒过几次，也有人在深层次的梦中憋尿时，会醒多次，总睁不开眼，等等。
     这里可能有多种类型：
     (1)  {（A梦）（B梦）（C梦）}，是连续梦，好像连续电视剧；
     (2)  {A梦[B梦（C梦）] }，是递归梦，属于尾递归；
     (3)  { A梦上集[B梦上集（C梦）B梦下集] A梦下集 }，是递归梦，属于中递归。可能中间递归消耗能量比较多，较多体验者报告醒后头痛、昏沉；
     (4)  {A梦  [ （B梦）（C梦） ]  }，是递归-连续 混合梦。
…..,和可能还有其他类型.

　　作为调侃，给一个基于内容的梦型区别方法：递归梦(3)中，C梦完后，会回到B梦下集，B梦完后，会回到A梦下集，做梦人可能记得有明显的（像计算机程序）递归栈； 而在情况（2），做梦人已经记不清楚，需仪器记录后用模式识别等技术。这就引出了下面的：
　　
2 一个新的模式识别课题。对上述问题，有兴趣的研究者可借用仪器，先记录下脑电波数据流，然后用数据流挖掘的方法，如 挖掘聚类、分类、关联、干预，等等， 找出其中的模式或梦类的关系；特别是：从一个梦退出，返回上一层梦，或链接下一集梦的流模式，进行深入研究。估计是比语音识别还难的问题，有兴趣的不妨试试，是否能得到基金支持，那就难说了。
     下面的讨论是基于《盗梦空间》平台，将戏说戏，将戏说科学，有戏说，也有科学。
 
3 后续讨论的背景知识。
　　后续讨论稍微有点复杂，尽量由浅入深，压低到高中二年级数学题的难度。拟用通俗的方式，模仿了教科书[1]中关于图灵机停机问题的递归法证明过程；透过证明，明眼人能看得见康托（Georg Cantor，1845-1918）在证明“实数不可数”时用的对角线方法，其技术要点是“反身+否定”；这里只不过借用读者从前篇博文得到的本体知识和电影故事的启发，增加了点趣味性和通俗性。
 
4 本文主要结论

      为简捷描述思路，需要一些（类似于教科书文献[1，2]的）符号和术语。
　　用M表示梦的编码(可理解为源程序)，s是梦中要处理的字符串（它描述某对象），<M,s>称为一个“梦--串对”。M(s)表示梦中处理s, 而P表示一个通用的梦串对判定程序。
　　本文主要结论是：
　　命题 递归梦是不可判定的，即不可能设计这样一个通用程序P，它能检查一切的梦串对<M,s>对应的那个梦是否会醒过来。
　　 思路： 用反证法，假定这样的P存在。命题的难点和突破点都在“一切”二字，既然P对一切的梦串对<M,s>作出判定，那么，对特殊的梦串对也能判定。  
      于是，设计了一个特殊的梦串对<M,s>，在梦中调用程序P，P又调用梦串对<M,s>为参数，实现了梦里用程序处理梦，递归，最后推出了矛盾。证明方法类似于MIT 教科书[2] P.139 关于停机问题的第二个证明，即用递归方法的证明。　　
　　还需对符号做些说明：
　　P(<M,s>)=真，表示P分析梦串对的结论是：在梦M中去处理对象s ,一定会醒过来；
　　P(<M,s>)=假，表示P分析梦串对的结论是：在梦M中去处理对象s ,永不会醒过来，相当于进入盗梦空间的迷失域。
　　
　　有了这些准备，下面开始证明。：(如看起困难，直接跳到 第5小节）
　　证明 用反证法：假定有这样一个程序P，对任意的梦-串对<M,s>, P不会死循环，即能在有限步后得出结果P（<M,s>），结果值在集合{ture,false}中。
　　(1) 设计一个嵌套梦，其C语言程序如下，先给出语句，再解释：
bool  M ( s)
{  Do-some-thing( ); //这里做一些平凡的非递归的梦境；
　　OK = ! P (<M,s>);  // 据对P的假设，P在{true，false}中，而！表Not（否定）
                           　  　// 直观上借用了百姓说法，梦是反的
  return OK;
 }  
程序经仔细检查，除了假设满足条件的P存在以外，其他部位没有问题。
 （　　
（2）导出矛盾 其实大功已经告成，就在下列矛盾中：
　　如果在P的参数中（相当于二层梦）的M ( s)= 真; 则OK= ！P (<M,s>）=假, 推出最后结果M ( s)= 假;
　　如果在P的参数中（相当于二层梦）的M ( s)= 假; 则OK= ！P (<M,s>）=真, 推出最后结果M ( s)= 真;
    真个是“假作真时,真亦假”， 矛盾了。
　（3）矛盾根源： 都是P惹的祸。“P有限步后会出结果”是构造这个程序的基础，避免这个矛盾的唯一出路是P (<M,s>)无限循环，根本不出结果；换言之，满足条件的通用程序P不存在；
　结论  不可能设计这样一个通用程序P，不是程序员的水平问题，而是本质上的不可能。
     明眼人立即看出，这是 图灵机停机问题 在盗梦空间（递归类程序集合）上的一个投影。

   （4）典型问题答疑，为易理解，简答博友几个典型问题
　　(a) 评论8和11 ：在梦M (s)中调用P(<M.s>）.为什么看起不像传统的递归？
     答：设F是反编译器（例如，把EXE变成汇编源程序），P(<M.s>）=P(<F(M),s>),看起就是递归了。在教科书的中译本[2] P136-139中，通过打印程序自身的过程 SELF实现，SELF可看成是这个反编译器F；这部分内容不太难，但稍有点长。Sipser, Michael 的窍门在于，在语法上，利用“P有限步后会出结果”回避了句法（syntactic)上的递归（也就不需要深度控制），但在语义上是递归的。
　 (b) 评论8：把此文的程序中的P去掉，在评论8给出了那个程序及相关问题。
　　答：评论8构造的M(...！M(s)...)不合理，M(s)是否终止尚未判定，如果没有深度控制和初始值，运行时堆栈上会压入一系列否定算子，直到栈溢出死机；而如果有递归深度控制与初始值，则根据深度的奇偶性返回值，导不出矛盾。我们的，或文献[1,2]上的程序，加了P， 由P的通用性，知道P在有限步后，一定返回值 True 或False ，程序总体构造上就没有问题。

　
　5 严重的后果：由于不可能设计程序来检查 递归梦（其实，它也是一个程序）；盗梦者所设计的梦到底是梦幻般的的旅游还是不归路，就成问题了。
    通俗和严格常常难以两全，上述证明（或说明）的重点在思路和框架，有若干细节，写出来反而更难懂，欢迎内行批评指正。
     到此，我们可以说，递归梦很美，盗梦空间有风险，入梦探险需谨慎。

   参考文献
  [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页面）