图灵机接受所有语言，即使它们可以递归枚举。递归表示重复相同的规则集任何次数，而可枚举表示元素列表。 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，并且head将向右移动为：
文章图片
该移动将为δ（q2，a）=δ（q3，A，R），这意味着它将进入状态q3，将a替换为A，并且头部将向右移动为：
文章图片
移动δ（q3，Δ）=（q4，Δ，S），这意味着它将进入状态q4，该状态为HALT状态，并且HALT状态始终是任何TM的接受状态。
相同的TM可用过渡表表示：
| 状态 | 一种 | b | D． |
|---|---|---|---|
| q0 | （q1, A, R） | – | – |
| q1 | – | （q2, B, R） | – |
| q2 | （q3, A, R） | – | – |
| q3 | – | – | （q4, Δ, S） |
| q4 | – | – | – |
文章图片
