自动机图灵机

图灵机

图灵机是阿兰·图灵（Alan Turing）于1936年发明的，它是一种接受0型语法生成的递归可枚举语言的设备。

图灵机有很多功能：

• 它有一个外部存储器，可以记住任意长的输入序列。
• 它具有无限的存储能力。
• 该型号能够轻松读取磁带左侧或右侧的输入。
• 机器可以根据其输入产生一定的输出。有时可能需要使用相同的输入来生成输出。因此，在这台机器中，输入和输出之间的区别被消除了。因此，图灵机可以使用通用字母集。

图灵机的正式定义

图灵机可以定义为一组 7 个组件：

Q：有限状态集
Σ：有限输入符号集
T：磁带符号
q0：初始状态
F：一组最终状态
B：用作输入结束标记的空白符号
δ：转换或映射函数。

映射函数显示了从有限自动机的状态和带上的输入符号到下一个状态、外部符号和带头运动方向的映射。这称为三重奏或图灵机程序。

(q0, a) → (q1, A, R)

这意味着在状态 q0 中，如果我们读取符号“a”，它将进入状态 q1，将 a 替换为 X 并向右移动（R 代表右）。

示例：

为语言 L = {0 ⁿ 1 ⁿ} 构建 TM，其中 n>=1。

说明：

我们已经用PDA解决了这个问题。在 PDA 中，我们有一个堆栈来记住以前的符号。图灵机的主要优点是我们有一个磁带头，可以向前或向后移动并扫描传入的磁带。

我们将应用的简单逻辑是读出 A 标记的每个“0”，然后向前移动输入带以找到 1 将其转换为 B。现在，对所有 a 和 b 重复此过程。

现在我们将看看这个图灵机如何在 0011 上工作。

现在我们来看看这个图灵机是如何在0011上工作的。最初状态是q0，head指向0的情况是：

的运动为δ(q0,0)=δ(q1,A,R)，即进入状态q1，将0替换为A，头部向右移动为：

移动将是δ(q1,0)=δ(q1,0,R)，这意味着它不会改变任何符号，而是保持不变并向右移动，如下所示：

运动将是δ(q1,1)=δ(q2,B,L)，这意味着它将进入状态q2，其中1被B替换，并且头部将向左移动：

现在，移动将是δ(q2,0)=δ(q2,0,L)，这意味着它不会改变任何符号，而是保持不变并向左移动：

运动将是δ(q2,A)=δ(q0,A,R)，这意味着将进入状态q0，A将被A替换，并且头部将向右移动为：

的运动为δ(q0,0)=δ(q1,A,R)，即进入状态q1，将0替换为A，头部向右移动为：

移动将是 δ(q1,B)=δ(q1,B,R)，这意味着它不会改变任何符号，而是保持不变并向右移动，如下所示：

运动将是δ(q1,1)=δ(q2,B,L)，这意味着它将进入状态q2，其中1被B替换，并且头部将向左移动：

移动 δ(q2,B)=(q2,B,L) 表示不改变任何符号，保持不变并向左移动如下：

现在B之前是A，也就是说所有的0都被A卖出了。因此，我们将继续执行以确保不存在1。移动将是 δ(q2,A)=(q0,A,R)，这意味着它将进入状态 q0，不会改变任何符号，并向右移动为：

移动δ(q0,B)=(q3,B,R)，这意味着它将进入状态q3而不改变任何符号并向右移动为：

移动 δ(q3,B)=(q3,B,R) 表示不改变任何符号，保持相同状态向右移动，如下：

移动δ(q3,Δ)=(q4,Δ,R)表示将进入状态q4，即HALT状态，而HALT状态始终是任何TM的接受状态。

同一个TM可以用转移图来表示：