学生：您能不能以一个简单易懂的方法描述一下图灵机和停机问题。

老师：20世纪30年代，大家都在讨论一个问题，什么是可计算的？一个计算机学家说，计算机是一门非常实用的学科，但它起始于一个哲学问题。这个哲学问题就是：什么是computable？当时有很多人想这个问题，一共有四五种关于可计算的刻画，有图灵机、哥德尔的递归函数、波斯特函数、丘奇的λ可定义。最后惊奇地发现所有这些刻画的函数类是同一个类，丘奇论题说可计算的就是图灵可计算，就是递归的。最吸引人的概念就是图灵的可计算性。

图灵机是什么？这一台图灵机，这是一个读写头，相当于我们的眼睛和手，模仿的是人在计算的时候你干什么。看一眼，写一下，看一眼，写一下，又读又写。人里面有大脑，它有它的状态和内部的指令。另一个就是一张纸，是一些它可以想象向两边无限延长的格子。这个格子只有两种情况，一种是空的，可以写个0，一种是1。读写头在这个上面来回地走。只做这几个动作，一个是向左移，一个向右移，每次一个格；一个是在空格上画下一道，一个是把原来上面有的道抹掉。

图灵机怎么算？比如算2+2=4，它在输入的时候2就是两个1，中间空一个格，再输入两个1。怎么输出4？有一套规则。把这两个移到这里，然后再把这两个抹掉，最后剩下一个4。

图灵机本身是可以编号的，因为它里面的状态都是有穷的。为图灵机编一个号，就可以把所有的人能造出来的图灵机都列出来。这就是一个自然数，这样都列出来，每个都有编号，也可以看作一个算术问题，可以算。停机问题是说，你有没有一个统一的图灵机来算，当某一个图灵机有一个输入的时候，是不是一定会停下来？停机问题在图灵机是不可解的。