递归梦的判定性与图灵停机问题.doc

递归梦的判定性与图灵停机问题--盗梦空间科普札记之三
本文试图通俗地描述盗梦空间中的江湖险恶,想说明“递归梦是否停止”这一问题是不可判定的,设计中稍有不慎,递归梦就是不归路。
     为了区别现实与电影,先考察:
1 递归梦与连续梦  
     人真的会做嵌套梦吗?游客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]中关于图灵机停机问题的递归法证明过程;透过证明,明眼人能看得见康托( Cantor,1845-1918)在证明“实数不可数”时用的对角线方法,其技术要点是“反身+否定”;这里只不过借用读者从前篇博文得到的本体知识和电影故事的启发,增加了点趣味性和通俗性。
 
4 本文主要结论
       为简捷描述思路,需要一些(类似于教科书文献[1,2]的)符号和术语。
用M表示梦的编码(可理解为源程序),s是梦中要处理的字符串(它描述某对象),<M,s>称为一个“梦--串对”。M(s)表示梦中处理s, 而P表示一个通用的梦串对判定程序。
本文主要结论是:
命题递归梦是不可判定的,即不可能设计这样一个通用程序P,它能检查一切的梦串对<M,s>对应的那个梦是否会醒过来。
思路: 用反证法,假定这样的P存在。命题的难点和突破点都在“一切”二字,既然P对一切的梦串对<M,s>作出判定,那么,对特殊的梦串对也能判定。   
       于是,设计了一个特殊的梦串对<M,s>