狗狗才

1936年24岁的英国大学生图灵设计了一个机器

它的组成不能再简单了，一条无限长的纸带，一个读写头，和一些规则。纸带上有很多小格子，里边可以写东西；读写头上有一个铅笔，和一个橡皮，还有一个记忆自己状态的寄存器，读写头对着纸带上的某一格。现在简陋的它就已经完全可以跟我们见过的所有强大的计算机算一样的题了。

关键在于规则定的好不好，比如我说，读写头在自己状态是q1的时候，如果看见纸带上写着0，则用橡皮把0擦掉，用铅笔写上1，把自己的状态改成q2并且往右移动一格。这就是一条规则。为了使它显得酷一点，我这样写：

R表示向右移动，当然还可向左移动L，不动N。所以一台图灵机可能的全部动作就是，看看自己状态是什么，再看看纸带上写什么，从规则里边找一条符合自己现在状态的，按着状态说的做，也无非就是把0改成1，或把1改成0，或者不改，然后向左走，或者向右走，或者不动。酷一些的写法是这样：

---------------------------------------------------------------------没有耐心的分割线---------------------------------------------------------------------

如果你不是非常有兴趣而且非常有耐心，那这段可以不看了。这里举例，图灵机是怎样算3+2的。（例子来自wikipedia）
用1的个数表示数值，算加法，两个数值间用0隔开，111011，就是3+2的意思。规则如下：
q0,0 -> q0,0,R
q0,1 -> q1,1,R
q1,0 -> q2,1,R
q1,1 -> q1,1,R
q2,0 -> q3,0,L
q2,1 -> q2,1,R
q3,0 -> -
q3,1 -> q4
第一行程序q0,0 -> q0,0,R意思就是如果机器读到0，就将其变成0，状态变为0，读写头向右移动一格。R就是向右移动一格，L就是向左移一格。q0是开始状态， - 是不接受的状态表示有错误，q4是接受状态表示已经得出正确结果。

步数 状态 纸带
1 0 01110110
2 0 01110110
3 1 01110110
4 1 01110110
5 1 01110110
6 2 01111110
7 2 01111110
8 2 01111110
9 3 01111110
10 4 01111100（停机）

停机后，纸带上有5个1，正是要求的结果。

---------------------------------------------------------------------没有耐心的分割线---------------------------------------------------------------------

图灵机的模型出现之后，人们所做的一切事情，只不过是找到真实的材料依照图灵的模型来造一台真实的机器罢了，而现在更加仅仅是提高这些真实机器的运算速度罢了。

图灵机在计算机理论中比比皆是，我感觉好像 90% 的定义都跟图灵机有关系。这是因为这个理想中的机器从“能力”上跟所有真实的运算机器等价。也就是说，所有的计算机能算的题图灵机都能算，图灵机不能算的题其他计算机也算不了。于是研究什么问题是能算的，什么问题是不能算的，也就是“可计算理论”的基础（这一部分也非常有趣，考虑以后写写看），都是由图灵机来承担的，P与NP问题的定义也与图灵机息息相关。

这片似乎相比之下比较难懂哈？最后做个小预告，下一篇我们将讲到多项式时间与指数时间的时间复杂度，P与NP最后一个要讲的定义拉，哈哈，然后就可以彻底揭示P跟NP是啥啦，敬请关注：）