一、图灵机的通俗比喻

        我们可以把图灵机看成是一部磁带播放器。通常磁带播放器会有一个磁头，一开始该磁头放在磁带的某个位置（比如我们希望从这部分开始播放），当我们按下播放键后，磁带便开始往某个方向（假设是顺时针方向）转动，然后我们就可以听到旋律优美的《我心永恒》啦。当《我心永恒》放到一半的时候，我们想从头再听一次，于是我们按下倒带键，于是磁带开始逆时针转动，一直到《我心永恒》的开头部分才停下来，然后继续顺时针转动，从头播放《我心永恒》。当《我心永恒》播放完毕后，随着磁带播放器发出“咔“的一声，磁带到达结束位置并停止转动了。

二、图灵机的定义

        有了上面的比喻，我们可以比较轻松地给出图灵机的正式定义。通常，大佬们会用i一个七元组（可以理解成装有七个不同玩意的袋子）<Q，T，B，∑，δ，q0，F>，其中

        Q：是一个有限的状态集合，在上面的例子中我们有四个状态（即未播放、播放、倒带和停止播放这四个状态）；

        T：是磁带字符表。我们知道磁带上存有一些信息（如一首歌或一段录音），于是我们可以把磁带看成是一个大的长方形别墅，在这个别墅里有很多并列的房间，每个房间里住着一个旋律或声音。当所有房间的旋律按顺序排列后，便形成了一首优美的歌曲。所以磁带字母表就相当于住在房间里的所有符号的集合（如前面的旋律），这些符号可以被磁头读取，也可以被磁头重写。

        B：顾名思义，即blank（空白的），表示空白字符；

        ∑：输入字符表。因为图灵机是一个完整的系统，而一个系统通常有输入和输出，图灵机接收的输入是字符序列，所以∑组成这些字符序列的基本单位。举个栗子，假设图灵机的输入是aabab，那么∑ = {a, b}。输入字符表和磁带字符表的关系是：∑ ⊆ T，即磁带字符表包含输入字符表，这不难理解，因为在对输入进行处理的过程中，不可避免地要用到一些临时符号。

        δ：是一个转换方程，即δ = Q × T → Q × T × {L,R}。下面解释这个表达式，首先看下”ד这个符号表示笛卡尔积，即给定两个集合A、B，A×B = { (x, y) | x ∈ A, y ∈ B}。举个栗子，A = {0,1}, B = {e, f}，那么A×B = { (0, e), (0, f), (1, e), (1, f) }。因此，这个转换方程的含义就很容易理解了，它的输入是一个状态和一个字符，根据该状态和输入字符，图灵机将决定输出下一个状态是啥、是保持该字符不变还是用另一个字符来替换该输入字符、下一步磁头将指向哪个格子（向左移动还是向右移动）。假设图灵机当前状态是q1，磁头指向的磁带格子(假设磁带是一个数组，每个格子存储的字符相当于数组的元素) Tape[2]上存储着字符”a“，经过转换方程后，图灵机的当前状态变为q2，Tape[2]上的字符由原来的”a“变为"b", 并且磁头当前指向Tape[3]。

        q0：表示初始状态，在第一部分例子中，其初始状态是未播放状态；

        F：表示终止状态，通常是一个集合，因为一个系统终止的原因有很多种，如正常完场任务后终止、遇到错误终止、人为强制终止等。在第一部分例子中，终止状态只有一个，即停止播放状态。