问题解决的“计算”之道
• 20世纪20年代，为了解决数学本身的可检验性问题，
大数学家希尔伯特提出“能否找到一种基于有穷观点
的能行方法，来判定任何一个数学命题的真假”
抽象的“计算”概念提出：
• 由有限数量的明确有限指令构成；
• 指令执行在有限步骤后终止；
• 指令每次执行都总能得到正确解；
• 原则上可以由人单独采用纸笔完成，而不依靠其它辅助；
• 每条指令可以机械地被精确执行，而不需要智慧和灵感。
关于“计算”的数学模型
• 20世纪30年代，几位逻辑学家几乎同时各自独立提出了几个关于“计算”的数学模型
• 奥地利逻辑学家、数学家哥德尔(K.F. Godel,1906-1978)和美国逻辑学家、数学家克莱尼(S.C. Kleene,1909-1994)的递归函数模型
• 美国逻辑学家、数学家丘奇(A. Church,1903-1995)的Lambda演算模型
• 波兰裔美国逻辑学家、数学家波斯特(E.L. Post,1897-1954)的Post机模型
• 英国逻辑学家、数学家图灵(A.M. Turing,1912-1954)的图灵机模型
基于有穷观点的能行方法
• 后续研究证明，这几个“基于有穷观点的能行方法”的计算模型，全都是等价的
• 在某个模型下“可计算”的问题，在另外的模型下也是“可计算”的
• 虽然希尔伯特的计划最终被证明无法实现
• 即不存在“能行方法”来判定任何一个数学命题的真假
• 总有数学命题，其真假是无法证明的
• 但“能行可计算”的概念，成为了计算理论的基础
• 其中的一些数学模型（如图灵机）也成为现代计算机的理论基础
图灵机Turing Machine
• 1936年，Alan Turing提出的一种抽象计算模型
• 基本思想是用机器模拟人们用纸笔进行数学运算的过程，但比数值计算更为简单
图灵机基本概念
• 在纸上写上或擦除某个符号；
• 把注意力从纸的一个位置转向另一个位置
• 在每个阶段，人要决定下一步的动作，依赖于：此人当前所关注的纸上某个位置的符号和此人当前思维的状态。
本文是基于北京大学地球与空间科学学院陈斌教授课堂实录整理的学习笔记。
