接受的语言和决定的语言

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

如果 TM 接受一种语言，则它决定该语言，并对任何不属于该语言的输入进入拒绝状态。如果语言由图灵机决定，则该语言是递归的。

在某些情况下，TM 可能不会停止。这样的 TM 接受语言，但并不决定语言。

设计图灵机

下面通过几个例子解释了设计图灵机的基本准则。

示例 1

设计一个 TM 来识别所有由奇数个 α 组成的字符串。

解决方案

图灵机 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₃ 中，它将用 0 替换 B，向左移动并达到最终状态 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}>

其中 δ 由下式给出 −