图灵机

一个图灵机是一种抽象的计算模型，它通过读取和写入无限磁带来执行计算。图灵机为解决计算机科学中的问题和测试计算的极限提供了一个强大的计算模型——是否存在我们根本无法解决的问题?图灵机是类似的有限自动机/有限状态机但有无限内存的优势。它们能够模拟普通计算机;一个普通计算机可以解决的问题(如果有足够的内存)也可以用图灵机解决，反之亦然。图灵机是由一位受人尊敬的计算机科学家发明的阿兰·图灵在1936年。

这是一个图灵机，检查输入字符串是否是回文。

在图灵机编程的指导下，磁带头沿着磁带读取和写入符号。

图灵机由无限大组成磁带(作为内存)，一个带头(一个指向当前被检查的内存单元的指针)和一个状态转换表(用来控制机器的行为)。磁带的每个单元格可以有一个预先确定的有限符号集，其中一个是空白符号。

图灵机，像算法一样，在输入上执行字符串的位．首先，输入的字符串写在磁带上，磁带头指向字符串的第一个单元格，所有其他单元格都是空白。

在操作过程中，磁带头处于某种状态。每一步，它都只根据它所处的状态和头下面的符号查询表(转换函数集)，以获得下一个选择:要么停止(结束操作)，要么通过向当前单元格写入符号、改变其状态并向左或向右移动来继续。通过这种方式，图灵机可以模拟一个程序是由许多行组成的，因此它取决于程序执行的是哪一行，它还可以模拟一个程序可以对内存中的不同数据做出不同的反应。

图灵机可以在某个点上停止，也可以永远运行。如果它停止，则输出磁带的内容。

网上有很多图灵机模拟器，比如这个模拟器这创建了上面的示例。

如上面的动画所示，图灵机由一个用一串符号初始化的磁带组成。这台机器有一个头部，当它沿着磁带移动时，可以读取和写入符号。

当磁带读取任何特定的符号时，它根据与机器相关的转换函数集来决定要做什么(在这一点上向磁带写入什么，然后向哪个方向移动)。转换函数本质上是图灵机程序中的一条特定指令行。您可以将转换函数集视为完整的程序，它指定图灵机对接收到的任何有效输入应该做什么。

在实践中，转换函数采用以下形式(参见下面的a正式的定义)．

• 我现在是什么状态啊

• 我刚才看到的是什么符号

• 我该写什么符号

• 接下来我应该变成什么样的状态

• 下一步我应该往哪个方向移动

这些输入的顺序取决于您使用哪个图灵机模拟器来运行您的机器，但所有这些信息都将包括在内。

状态可以看作是规则的子集。例如，如果图灵机有两种状态，当头部读取一个“a”符号处于状态时 $1$，机器可能会做一件事，如果头部读取一个“A”符号状态 $2$，它可以做不同的事情。

转换函数通常以表格形式表示。下表描述了一个简单的图灵机，它取一串 $1$的作为输入并将其加倍。所以" 11 "变成了" 1111 "等等。在下面的规范中，有三种状态:状态0、状态1和状态2。暂停是一种特殊的状态，可以用来表示程序已经结束。有2个符号:1和a。移动方向有三种选择:左、右和停留(用*表示)。

在这里，符号“A”用来表示我们已经看到的“1”，当我们读到“1”时，我们就写了一个“A”。这样我们就不会重复计算符号了。一旦我们把所有的1都换成了A，磁带上的所有符号都变成了A。然后，把所有的A都换成1，原来的字符串就翻倍了。

让我们在输入“111”上一步一步地运行这个字符串加倍的图灵机(如上表所述)(尽管这台机器会将任何1的字符串加倍)。

磁带下面的代码显示了转换函数。要执行的下一步用蓝色突出显示，上一步用橙色突出显示。

(注意在上面的模拟中，左边用小写字母L表示，右边用小写字母r表示)

图灵机的正式定义是7-元组 $\lang Q, q_0, F， \Gamma, b， \Sigma， \delta \rangle$,在那里

• $问$是有限的，非空的吗集的州
• $q_0 \在Q中$是初始状态
• $F \子集Q$是接受状态
• $\γ$的有限非空集合带符号
• $b \in \Gamma$是空白的象征
• $\Sigma \子集\Gamma \setminus \{b\}$是一套输入符号
• $\delta:(Q \setminus F) \times \Gamma \到Q \times \Gamma \times \{L, R\}$是转换函数，这是一个偏函数

图灵机的操作是一个序列 $(\ langle问‘_,h_s (t_ {s, p})识别_ {p = - \ infty} ^ \ infty \纠正)_ {s = 0} ^ \ infty$,在那里

• $q_s$是状态的磁带头 $年代$th一步
• $h_s$是位置的磁带头 $年代$th一步
• $t_{识别s, p}$是内容磁带的 $年代$-第一步和 $p$th位置

这样

• $Q '_0 = q_0$
• $H_0 = 0$
• 如果输入字符串为 $(x_1， \ldots, x_n) \in \Sigma^n$,然后 $T_ {0,p} = x_{p+1}$为 $0 \le p \le n-1$而且 $T_ {0,p} = b$否则
• 如果 $\delta(q_s, t_{s, h_s}) = (q, t, d)$,那么:
  • $Q_ {s+1} = q$
  • $H_ {s+1} = h_s - 1$如果 $d = L$, $H_ {s+1} = h_s +1$如果 $d = R$
  • $T_ {s+1, p} = t$如果 $P = h$, $T_ {s+1, p} = T_ {s, p}$否则
• 否则,如果 $q_s \in F$或 $\delta(q_s, t_{s, h_s})$没有定义，那么机器呢停止；其余的序列没有定义，并且 $年代$是步骤数由机器拍摄。

转换函数定义图灵机的规则或程序。转换函数通常用表格表示。转换函数编码图灵机在读取每个可能的输入时应该做什么 $\γ$)．本质上，转换函数是以下形式:“如果你读符号 $X$，您目前处于状态 $S_a$，写入符号 $Y$，搬进来这方向，并切换到状态 $S_b$”。在 $X$而且 $Y$表示中的某个符号 $\γ$而且 $S_a$而且 $S_b$这些州 $Q。$一条指令可能会说“写你读到的相同符号”或“保持相同状态”——这完全取决于程序员定义转换函数。程序员必须写出一组适当的指令来完成手头的任务。

图灵机可以识别和决定不同类型的问题和语言。语言描述问题。例如，有一种语言的所有字符串都完全由1组成——这种语言的一些成员将是“1”、“111111”、“111111111”等。我们可以制造图灵机来计算这些字符串。例如，写一个程序，让图灵机每次向右移动都写一个1，这样机器就会一直向右移动。

可认可

语言是可辨认的如果图灵机接受输入字符串，如果输入字符串不是该语言，则拒绝或永远循环。换句话说，如果一种语言是可识别的，那么图灵机可能不会停止处理该语言中不存在的字符串。

可判定性

语言是可决定的如果图灵机接受语言中的字符串而拒绝语言之外的字符串。换句话说，图灵机将在所有输入时停止。所有可识别的语言都是可识别的，但并不是所有可识别的语言都是可判定的。的停止的问题是一个重要的例子，一个可识别的问题是不可判定的。

的Church-Turing论文任何可计算的问题都可以被图灵机计算出来。这意味着，解决可计算问题并不需要比图灵机更强大的计算机。图灵完备性的思想与此密切相关。如果一个系统能计算每个图灵可计算函数，那么它就是图灵完备的。图灵完备的编程语言理论上能够表达计算机可以完成的所有任务;几乎所有的编程语言都是图灵完备的。

为了证明某物是图灵完备的，证明它可以模拟其他的图灵完备系统就足够了。通常，最简单的方法是证明一个系统可以模拟通用图灵机．通用图灵机是一种可以模拟的图灵机任何其他图灵机。

• 有限状态机

• 停止问题

• 通用图灵机

• Church-Turing论文

• 多带图灵机

• 非确定性图灵机