图灵机

图灵机由艾伦·图灵于 1936 年发明。它是一种接受设备，接受由零型文法生成的递归可枚举语言。

图灵机有各种特性

1. 它具有外部存储器，可以记住任意长的输入序列。
2. 它具有无限的内存能力。
3. 该模型具有方便的设施，可以轻松读取磁带上左右两侧的输入。
4. 机器可以根据输入产生一定的输出。有时可能需要使用相同的输入来生成输出。因此，在此机器中，输入和输出之间的区别已被消除。 thus a common set of alphabets can be used for the Turing machine。

图灵机的形式定义

图灵机可以定义为由 7 个组件组成的集合

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

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

也就是说，在 q0 状态下，如果我们读取符号 'a'，它将进入状态 q1，将 a 替换为 X，然后向右移动（R 代表右）。

示例

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

解决方案

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

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

现在我们将看到这个图灵机如何处理 0011。

现在，我们将看到这个图灵机如何处理 0011。最初，状态是 q0，磁头指向 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 可以用转换图表示