接受的语言和确定的语言

如果图灵机对任何输入字符串 w 进入最终状态，则它接受该语言。如果图灵机接受一种语言，则该语言是可枚举递归的（由 0 型文法生成）。

如果图灵机接受一种语言并且对语言中不存在的任何输入进入拒绝状态，则它判定该语言。如果图灵机判定一种语言，则该语言是递归的。

在某些情况下，图灵机可能不会停止。这样的图灵机接受该语言，但它并不判定它。

图灵机设计

下面将通过几个例子解释图灵机设计的基本指导原则。

示例 1

设计一个图灵机来识别所有包含奇数个 α 的字符串。

解决方案

图灵机 **M** 可以通过以下步骤构建：

• 设 **q₁** 为初始状态。

• 如果 **M** 处于 **q₁** 状态；扫描到 α 时，它进入 **q₂** 状态并写入 **B**（空格）。

• 如果 **M** 处于 **q₂** 状态；扫描到 α 时，它进入 **q₁** 状态并写入 **B**（空格）。

• 从上述步骤可以看出，如果 **M** 扫描到偶数个 α，它将进入 **q₁** 状态；如果它扫描到奇数个 α，它将进入 **q₂** 状态。因此，**q₂** 是唯一的接受状态。

因此，

M = {{q₁, q₂}, {1}, {1, B}, δ, q₁, B, {q₂}}

其中 δ 由下式给出：

示例 2

设计一个图灵机，读取表示二进制数的字符串，并擦除字符串中所有前导的 0。但是，如果字符串只包含 0，则保留一个 0。

解决方案

让我们假设输入字符串在字符串的每一端都以空格符号 B 结尾。

图灵机 **M** 可以通过以下步骤构建：

• 设 **q₀** 为初始状态。

• 如果 **M** 处于 **q₀** 状态，读取 0 时，它向右移动，进入 **q₁** 状态并擦除 0。读取 1 时，它进入 **q₂** 状态并向右移动。

• 如果 **M** 处于 **q₁** 状态，读取 0 时，它向右移动并擦除 0，即用 B 代替 0。到达最左边的 1 时，它进入 **q₂** 状态并向右移动。如果它到达 B，即字符串只包含 0，则它向左移动并进入 **q₃** 状态。

• 如果 **M** 处于 **q₂** 状态，读取 0 或 1 时，它向右移动。到达 B 时，它向左移动并进入 **q₄** 状态。这验证了字符串只包含 0 和 1。

• 如果 **M** 处于 **q₃** 状态，它将 B 替换为 0，向左移动并到达最终状态 **q_f**。

• 如果 **M** 处于 **q₄** 状态，读取 0 或 1 时，它向左移动。到达字符串的开头，即读取 B 时，它到达最终状态 **q_f**。

因此，

M = {{q₀, q₁, q₂, q₃, q₄, q_f}, {0,1, B}, {1, B}, δ, q₀, B, {q_f}}

其中 δ 由下式给出：