2.2图灵机工作原理

                                    第三周学习单

一、课程阅读（约30min）

   国际著名计算科学家马纳曾在其著作《计算的数学理论》开头写道：“什么是计算？我相信世界上没有两个计算机科学家会就这一概念给出相同的定义。”而我们这一节给出的也只是图灵对于计算模型的一个阐述。

1、关于计算

我们这节课从三次数学危机开始讲什么是计算，数学的研究起源于对计算的研究。但是要明白一点，数学不等于计算。对于一个问题如何找到解决的方法和步骤，这就是可计算问题。

计算学科的一个基本结论就是不可计算的函数要比可计算的函数多的多。

那么有些问题可以计算（可以理解为，用一张纸和笔做有限次运算就可以完成），有些问题不可以计算（也就是无法用有限的步骤来解决），那么如何在两者之间划一个边界，这就是可判定问题，也是图灵的研究主题，才有了图灵机。

2、图灵机工作原理

（https://www.cl.cam.ac.uk/projects/raspberrypi/tutorials/turing-machine/one.html ）这个链接是剑桥大学计算机网站上给出的图灵工作原理的解释图，大家可以配合这个视频（   

 https://www.cnblogs.com/willick/p/algorithms-03.html ）做课前理解。（约30min）

二、课程导图

三、课后

     今天我们在将图灵机工作原理的时候，将他和我们熟知的大富豪游戏联系起来，并且可以证明两者其实是等价的。那么对图灵机的任何不理解的地方，转换到游戏环节来理解。这其实也是创新的方法之一，就是联系，科学史上有非常多相关的案例。通过跨领域联系的方式来解决本领域的问题。

比如对于解答人类是什么时候穿上衣服的。这个问题一直困扰着考古学家和人类学家。因为衣服的材料不是动物皮毛、就是植物纤维，这些东西都没有办法长期保存，根本就不可能保留一些给今天的考古学家来研究。但是德国的生物遗传学家马克.斯托金教授却利用基因检测破解了这个难题。1999年，教授收到学校通知说，他的孩子班里最近出现了虱子，请家长注意孩子卫生。由此教授想到了虱子寄生在人类身上，无法独立生存，那么可否用研究虱子DNA的方法来研究人类的历史呢？人类不穿衣服的时候，虱子是生活在毛发里的，称为头虱，当人类穿上衣服后，就有一部分虱子从头发里跑下来，进到了衣服里面来生存。时间久了，生活在头发里的虱子和生活在衣服里的虱子，在基因方面就发生了变化。所以只要确定了头虱和体虱的分开时间，就可以推导出人类穿上衣服的时间。根据这种方法，斯托金教授最终推导出：我们人类最早穿上衣服，大概在10.7万年前。

再比如，获得诺贝尔医学奖的卡雷尔，被称为血管缝合之父，在19世纪末血管缝合在材料和方法上都是一个难题，而卡雷尔则参照了，自己做纺织工作的母亲的纺织手法，发明了三点缝合术，解决了这一问题。

我平时在理解很多自己不明白的问题的时候，也都是采用这种方法。比如之前很长一段时间，我不太理解莎士比亚在英国史上为什么如此重要，丘吉尔说，“我宁可失去一个印度，也不愿失去莎士比亚”。文学作家而已，何至于此？但是如果我把他类比成李白，其重要程度不言而喻，李白的诗篇清新俊逸，豪迈奔放，如果在中国文学史上少了这一笔，该有多大的遗憾。所以我也推荐大家，对于自己不理解的问题，不理解的领域不妨迁移到容易理解的角度去看，说不定会有意想不到的收获。

而科研创新也好还是创业创新也好，除了联系还有一点就是观察，这两点也是我在课程中着重强调的地方。比如计算机网络这一章，前两天做调查问卷的时候，有同学说不感兴趣，的确如果仅从知识点的角度看，确实没什么意思。但是如果你能和电话网络，或者生活中的人际网络，疾病传播网络联系在一起看，就能发现他们之前的共性和联系。万物之始，大道至简。