Lambda初级简介 - 图灵机
图灵在1936年发表的论文— 《论可计算数及其在判定问题上的应用》堪称是20世纪最伟大几篇论文之一。众所周知，图灵机作为人类迄今为止发明的可以被实现的最强大的计算模型，在数学、计算机科学、哲学、物理学等多种学科中具有十分重要的地位。可以说是人类对计算认知的基石（超计算模型普遍以神谕机为原型— 一种特殊的图灵机）。理解图灵机及其重要意义是理解现代计算机的基础。
本系列文章受我个人水平限制，将会以十分简单 （而不是简易、简略或简明） 的方法介绍Lambda和图灵机的有关内容。而且必定会出现知识性错误，请读者自行判断是否准确，切勿完全相信本系列文章的表达。
好，继续介绍图灵机。
理解图灵机，最好的方法就是去读图灵的论文。限于本人水平问题，故无法完全解析这篇论文。所以本篇介绍图灵机的文章仅仅对其概念进行一个简单的介绍。论文本身论证了只要是图灵机（严格来讲是自动图灵机，a-machine，我们这里讨论的就是自动图灵机并省略自动这个修饰词）能够解决任何可计算问题。
图灵机与lambda等价，且与任何图灵完全（该计算模型可以计算所有图灵机可以计算的问题，或者说可以模拟图灵机的行为）的计算模型等价。但是之所以图灵机被誉为计算模型的根本，其原因是图灵机不光具有数学上的理论价值，而且还具备一丢丢的实际价值（图灵机是一个数学模型，但是本身就像是一台“机器”）。一个人一支笔一张纸就能在不接受任何高等教育的基础上模拟完成图灵机，事实上，也有人用乐高玩具模拟了图灵机（很好玩的视频）。
图灵机由以下部件构成：
- 一条无限长的纸带（tape），被分割成一个一个的小格子（square），每个格子仅能存放一个符号（symbol）。
- 一个读写头，可以在纸带上读取、写入或擦除纸带上当前指向格子里的字符，也可以左右移动一个格子
- 一个由所有可能的符号组成的有限集合
- 一个存放图灵机当前的内部状态（m-configuration）的寄存器
图灵机一次能且仅能读取在纸带上的一个字符，该字符被叫做S(r)。图灵机的内部状态被叫做q(n)。这两个状态决定了图灵机当前的配置（configuration），而该状态决定了图灵机接下来的行为。图灵机的行为无非就是“删除当前字符”、“写上一个字符”、“左移一格”、“右移一格”和“什么也不做”。同样，字符也包括“什么也没有”。我们将内部状态和字符决定的一系列操作的所有可能性的集合称为指令集，由于一台图灵机的所有字符和所有状态都是有限的，所以指令集也是有限集合。
就这样，三个集合构成了一台图灵机！而纸带则是输入，可以为空。
图灵机的构造十分简单，以至于我无话可说。但是蕴含在这简单构造的背后是足以计算一切可计算数的计算能力。图灵证明了图灵机可以计算一切可计算问题。而另外一个重要的论题”丘奇-图灵论题“则提出了是否一切计算和算法都可以用图灵机计算。同时，用图灵机计算的特征之一就是在有限多的步骤以有限多的指令集完成计算。目前学界普遍接受该论题为真（尽管无法证明）。
下面来看一个图灵机的例子:
我们使用一个在线的图灵机模拟器来模拟图灵机。它的界面十分简洁明了。上方是图灵机的模拟区，输入框里可以给纸带载入任何字符，右侧的滑块调整模拟速度，中间则是控制步进的。
下方的文本框是编程区域，其使用的语言十分简单。
来看一段翻转字节的图灵机代码
1 | name: Revert bits //定义图灵机的名字 |
是不是很简单？
图灵机就是这些！