图灵机

图灵机是一个计算模型, 包括以下几个要素：

1.无限长的带子, 是符号记录的载体。

2.读写头, 可以左右移动, 可以读出和改变带上的符号。

3.状态寄存器, 用于保存图灵机当前的状态。

4.控制规则, 根据读写头的状态和带上的字符改变状态寄存器的值，并确定下一步动作。

图灵机可以用于计算函数值。

例如：$f(x,y)=x+y$$f (x, y) = x + y$

通常, 变量可以有多种表示方式。如果$x=4$$x=4$, 十进制的表示法是"4"; 二进制的表示方式是"100"; 一元数(Unary)表示法则是"1111". 图灵机倾向于使用一元数表示法。

采用4元控制规则：$q_1{S}_0{q}_{2}R$$q_1S_0q_2R$; $q_1{S}_1{q}_1{S}_0$$q_1S_1q_1S_0$; $q_2{S}_0{q}_3{S}_1$$q_2S_0q_3S_1$; $q_2{S}_1{q}_{2}R$$q_2S_1q_2R$; $q_3{S}_0{q}_{4}R$$q_3S_0q_4R$; $q_3{S}_1{q}_{3}L$$q_3S_1q_3L$

编程模拟图灵机的运行过程:

图灵机运行结束时, 得到$f(x,y)=5$$f(x,y)=5$, 仍使用一元数表示法。

结束的状态如图所示：

图灵机是理论计算机。条带对应于输入和输出数据, 控制规则对应于程序。

图灵机的定义是：$M=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_1,q_{accept},q_{reject})$$M=(Q,\Sigma,\Gamma, \delta, q_1,q_{accept},q_{reject})$, 其中:

• $Q=\{q_1,q_2,\cdots ,q_{accept},q_{reject}\}$$Q=\{q_1,q_2,\cdots,q_{accept},q_{reject}\}$.
• 起始(start)状态、接受(accept)状态和拒绝(reject)状态分别为$q_1$$q_1$, $q_{accept}$$q_{accept}$, $q_{reject}$$q_{reject}$.
• 输入符号集(Input Alphabet) $\mathrm{\Sigma }$$\Sigma$.
• 条带字符集(Tape Alphabet) $\mathrm{\Gamma }$$\Gamma$​，包含一个空符号(Blank Symbol): $\bigsqcup$$\sqcup$​. 这里$\bigsqcup \in \mathrm{\Gamma }$$\sqcup{\in}\Gamma$​,但$\bigsqcup \notin \mathrm{\Sigma }$$\sqcup{\notin}\Sigma$​. $\mathrm{\Sigma }\subseteq \mathrm{\Gamma }\setminus \{\bigsqcup \}$$\Sigma\subseteq\Gamma\setminus\{\sqcup\}$​.​
• $\delta :(Q\setminus \{q_{accept},q_{reject}\})\times \mathrm{\Gamma }\to Q\times \mathrm{\Gamma }\times \{L,R\}$$\delta: (Q \setminus \{q_{accept},q_{reject}\}) \times \Gamma \rightarrow Q \times \Gamma \times \{L,R\}$, 其中$L,R$$L,R$表示左右移动。

控制规则($\delta$$\delta$)的几种表示方法：

• 4元组(4-Tuple)表示法
• 5元组(5-Tuple)表示法
• 表格(Table)表示法
• 状态图(State Diagram)表示法

这些表示法可以互相转换。

加法图灵机$\delta$$\delta$的5元组表示法：

• $q_1{S}_1{q}_2{S}_{0}R$$q_1S_1q_2S_0R$
• $q_2{S}_0{q}_3{S}_{1}L$$q_2S_0q_3S_1L$
• $q_2{S}_1{q}_2{S}_{1}R$$q_2S_1q_2S_1R$
• $q_3{S}_0{q}_4{S}_{0}R$$q_3S_0q_4S_0R$

相比4元组表示法, 5元组表示法的每条控制规则中, 既包含下一步的状态, 又包含下一步的移动方向。

加法图灵机$\delta$$\delta$的表格表示法：

下图是一个实现$f(x)=2x$$f(x)=2x$​的图灵机对应的状态图:

其中, $q_1$$q_1$是初始状态, $q_{12}$$q_{12}$是终止状态。此状态图表示法与4元组表示法对应。

图灵机是强大的。凡是程序算法能解决的问题，一定能通过图灵机解决；反过来，凡是图灵机解决不了的问题，任何程序算法也解决不了。