图灵机

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

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

根据图灵机的编程指令，磁带头沿着磁带的读写符号移动。

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

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

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

因此，图灵机要么在某个点停止，要么永远运行。如果它停止，磁带的内容就是输出。

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

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

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

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

• 我现在是什么状态啊

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

• 我该写什么符号啊

• 我下一步该变成什么状态

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

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

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

转换函数通常以表格形式表示。下表描述了一个简单的图灵机，它取一个字符串 $1$作为输入并将其加倍。所以“11”变成了“1111”，以此类推。在下面的规范中，有三种状态:状态0、1和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 \ range$,在那里

• $问$是有限的，非空的吗集的州
• $在问q_0 \$是初始状态
• $F \子集问$是集合接受状态
• $\γ$是有限的，非空的集合带符号
• $b \ \γ$是空白的象征
• $\Sigma \子集\Gamma \setminus \{b\}$是一套输入符号
• $\delta:(Q \setminus F) \times \Gamma \to 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}$是内容磁带的 $年代$th一步, $p$th位置

这样

• $问' _0 = q_0$
• $h_0 = 0$
• 如果输入字符串是 $(x_1， \ldots, x_n) \in \Sigma^n$,然后 $t_ {0, p} =识别间{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} =问$
  • $H_ {s+1} = h_s - 1$如果 $L d =$, $H_ {s+1} = h_s +1$如果 $d = R$
  • $T_ {s+1, p} = t$如果 $p = h_s$, $T_ {s+1, p} = T_ {s, p}$否则
• 否则,如果 $在F q_s \$或 $\δ(q_s t_{年代,h_s})识别$没有定义，那么机器呢停止；序列的其余部分没有定义，并且 $年代$是许多步骤被机器带走了。

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

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

可认可

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

可判定性

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

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

要证明一个东西是图灵完备的，只要证明它可以模拟其他的图灵完备系统就足够了。通常，最容易证明的是一个系统可以模拟一个通用图灵机．通用图灵机是一种可以模拟的图灵机任何其他图灵机。

• 有限状态机

• 停止的问题

• 通用图灵机

• Church-Turing论文

• Multi-tape图灵机

• 不确定性图灵机