图灵机接受的语言

图灵机接受所有语言，即使它们是递归可枚举的。递归意味着对任何次数重复同一组规则，可枚举意味着元素的列表。TM 也接受可计算函数，如加法、乘法、减法、除法、幂函数等等。

示例

构造一个图灵机，它接受 Σ = {a, b} 上的语言 aba。

解决方案

我们将假设输入带上放置的字符串 'aba' 如下所示

磁带头将读出序列直到 Δ 字符。如果磁带头读出 'aba' 字符串，则 TM 将在读取 Δ 后停止。

现在，我们将看到这台图灵机如何处理 aba。最初，状态是 q0，磁头指向 a，如下所示

移动将是 δ(q0, a) = δ(q1, A, R)，这意味着它将进入状态 q1，将 a 替换为 A，并且磁头将向右移动，如下所示

移动将是 δ(q1, b) = δ(q2, B, R)，这意味着它将进入状态 q2，将 b 替换为 B，并且磁头将向右移动，如下所示

移动将是 δ(q2, a) = δ(q3, A, R)，这意味着它将进入状态 q3，将 a 替换为 A，并且磁头将向右移动，如下所示

移动 δ(q3, Δ) = (q4, Δ, S)，这意味着它将进入状态 q4，这是 HALT 状态，而 HALT 状态始终是任何 TM 的接受状态。

相同的 TM 可以用转换表表示

同一个 TM 可以用转换图表示