the computational model

最初的目标是构造一个计算的模型。这个模型可以看作一个集合，这个集合中的每个元素相当于某一个具体问题的解决方案，也就是一个“程序”；这个集合整体就是一个计算模型，也就是一个可以运行任何“程序”的“计算机”。所以构造一个计算模型的目标，分别从程序和计算机的角度就是要规定程序如何表达和程序如何运行。
直观上来说“计算”就是已有一些“数据”和一些的“草稿纸”，按照“解题思路”每次在数据和稿纸中拿出一些数据进行计算，将结果写在稿纸上或写在“答题纸”上。构造的计算模型应该符合这一直觉。
我们还希望这个模型具有“通用性”，也就是研究“计算”可以建立在这个模型基础上，而非将计算这个本质的概念特殊化，将“可计算”等问题的研究限定在当今世界中。这样，理论计算才能成为一门永恒的科学，而非日新月异的技术。

turing machine

图灵机的一些细节

一个图灵机可以看作一个程序。
纸带和针头（数据草稿纸）：多个纸带，纸带上面每个位置可以写单个字符，每条纸带有一个针头，每次可以向左或向右移动一个单位，也可不动。有一个输入纸带，表示给定的数据；一个输出纸带，在运行结束时输出纸带上的值就代表输出结果；其他纸带均用于存储中间运算的结果。设有\(k\)个纸带，纸带上字符集大小为\(\Gamma\)
状态（临时记忆）：状态只是一个抽象的数，但作为一个临时的记忆，可以存储的东西种类很多，例如“程序进行到第几步了”，“上一秒从纸带读入的数据是哪些”等等，但因为只是一个数，可以认为记录的信息量是关于读入\(O(1)\)的。状态是集合\(Q\)的一个元素。
计算一步的过程：从每个纸带的针头处读取一个元素，再根据读取的元素和目前的状态决定下一个状态，这些针头处的值如何修改，以及每个针头分别如何移动，或者选择结束计算。那么整个计算的运行时间就可以看作这样的计算的步数。
转移函数（解题思路）：由于修改和移动完全取决于针头处的值和目前的状态，因此可以将每次计算看作一个函数\(\delta:Q\times \Gamma^k \rightarrow Q\times \Gamma^{k-1}\times \{L,S,R\}^k\)。
值得注意的是，“状态”这个数不是可有可无的，比如说我想将纸带的某个位置的值\(x\)移到纸带末尾，那么我在移动的每一步“必须要记住\(x\)的值”，这个值是无法在纸带的读入中得到的，所以必须要将\(x\)的值作为一个临时记忆放在状态里以便转移。

定义的普遍性

先定义一个图灵机的运行时间：如果对于所有长度为\(n\)的输入，运行时间不超过\(T(n)\)，则称运行时间为\(T(n)\)。
可以从以下几点中感受图灵机模型定义的普遍性：字符集大小的任意性，纸带条数的任意性，纸带可以是双向延伸也可以是单向延伸。这里的任意性说的是在一种模型下的任一程序，可以对应到另一模型下的一个程序使得输出相同，且运行时间不慢太多。

对于任意\(k+2\)个纸带的图灵机，运行时间\(T(n)\)，存在三个纸带的图灵机得到相同的结果，运行时间\(kT(n)\log T(n)\)。

证明：将用于草稿的\(k\)个纸带变成一个纸带，字符集\(\Gamma\)变成\(\Gamma^k\)，然后\(k\)个针头的移动转化成\(k\)条纸带分别平移，直接暴力平移是\(kT(n)^2\)的。优化每条纸带的平移可以优化到\(T(n)\log T(n)\)，算法如下：类似倍增的方法，以针头为中间点，左右从中间向两边按\(2,4,8,...,2^k,...\)依次分块，保证\(2^k\)的块内有效元素个数为\(2^k\)或\(2^{k-1}\)或\(0\)，其他元素用空字符填充，且对称（块大小相同的两个块）内有效元素个数之和为\(2^k\)。以左移距离，先找到右侧第一个有效元素数不为\(0\)的块\(2^t\)，那么右侧\(2,4,8,...,2^{t-1}\)这些块为空。将\(2^t\)块内的\(2^{t-1}\)个元素取出，依次放到针头处，\(2,4,8,...,2^{t-1}\)这些块各填满一半，对于左侧，进行相反的操作，将针头处，\(2,4,8,...,2^{t-1}\)这些块的元素各拿出一半，放到\(2^t\)处。例如|oooo|aa|i|oo|bcdd|变为|ooaa|oi|b|co|ddoo|。注意到如果访问到\(2^k\)块，单次复杂度为\(O(2^k)\)，但此后至少\(2^{k-1}\)内不会再访问到\(2^{k-1}\)块，因此每块均摊复杂度\(O(T(n))\)。