什么是算法？算法就是图灵机
3.1 图灵机
图灵机用一个无限长的带子作为无限存储，它有一个读写头，能在带子上读、写和左右移动。图灵机开始运作时，带子上只有输入串，其他地方都是空的，如果需要保存信息，它可将这个信息写在带子上。为了读已经写下的信息，它可将读写头往回移动到这个信息所在的位置。机器不停地计算，直到产生输出为止。机器预置了接收和拒绝两种状态，如果进入这两种状态，就产生接收（accept)或拒绝(reject)，如果不能进入任何接收或拒绝状态，就继续执行下去，永不停止。
3.1.1 图灵机的形式化定义
D e f 3.1 Def\ 3.1 Def 3.1图灵机是一个7元组 ( Q , ∑ , Γ , δ , q 0 , q a c c e p t , q r e j e c t ) (Q,\sum,\Gamma,\delta,q_0,q_{accept},q_{reject}) (Q,∑,Γ,δ,q0,qaccept,qreject),其中: Q , ∑ , Γ Q,\sum,\Gamma Q,∑,Γ都是有穷集合，并且
- Q Q Q是状态集
- ∑ \sum ∑是输入字母表，不包括特殊空白符号 ⊔ \sqcup ⊔
- Γ \Gamma Γ是带子字母表，其中， ⊔ ∈ Γ , ⊳ ∈ Γ , ∑ ⊆ Γ \sqcup\in\Gamma,\rhd\in\Gamma,\sum\subseteq\Gamma ⊔∈Γ,⊳∈Γ,∑⊆Γ
- δ : Q × Γ → Q × Γ × { L , R } \delta:Q\times\Gamma\rightarrow Q\times \Gamma\times\{L,R\} δ:Q×Γ→Q×Γ×{L,R}是转移函数
- q 0 ∈ Q q_0\in Q q0∈Q是起始状态
- q a c c e p t ∈ Q q_{accept}\in Q qaccept∈Q是接收状态
- q r e j e c t ∈ Q q_{reject}\in Q qreject∈Q是拒绝状态，且 q r e j e c t ≠ q a c c e p t q_{reject}\ne q_{accept} qreject=qaccept
⊳ \rhd ⊳是最左端，转移函数 δ ( q , a ) = ( r , a , L ) \delta(q,a)=(r,a,L) δ(q,a)=(r,a,L)时，机器写下符号 b b b以取代 a a a，并进入状态 r r r，第三个分量指出时向左( L L L)还是向右( R R R)，
例：输入一个二进制数n，低位在前，输出n+1
| Input | OUTput |
|---|---|
| 101 ⊔ ⊔ 101\sqcup\sqcup 101⊔⊔ | 011 ⊔ ⊔ 011\sqcup\sqcup 011⊔⊔ |
| 11 ⊔ ⊔ 11\sqcup\sqcup 11⊔⊔ | 001 ⊔ ⊔ 001\sqcup\sqcup 001⊔⊔ |
∑ = { 0 , 1 } , Γ = { 0 , 1 , ⊔ , ⊳ } \sum=\{0,1\},\Gamma=\{0,1,\sqcup,\rhd\} ∑={0,1},Γ={0,1,⊔,⊳}，容易的，一直写0，直到遇到第一个为0或 ⊔ \sqcup ⊔的，改写为1，停下。
格局:图灵机计算过程中，当前状态、当前带子内容和读写头当前位置组合在一起，称为图灵机的格局。对于状态 q q q和带子字母表 Γ \Gamma Γ上的两个字符串 u u u和 v v v，以 u q v uqv uqv表示如下格局：当前状态是 q q q，当前带子内容是 u v uv uv，读写头的当前位置是 v v v的第一个符号，带子上 v v v的最后一个符号以后的符号都是空白符。
