图灵机是一种计算模型，如有限自动机 (FA)、下推自动机 (PDA)，适用于不受限制的语法。与 FA 和 PDA 相比，图灵机是最强大的计算模型。
形式上，图灵机 M 可以定义如下 -
M = (Q, X, ∑, δ, q0, B, F)
Q 表示有限的非空状态集。
X 表示磁带字母集。
∑ 表示非空的输入字母集。
δ 是转移函数，其映射为： δ : Q x X → Q x X x {Left_shift, Right_shift}。
q0 是机器的初始状态
B是空白符号
F 是最终状态或停止状态的集合。
单带图灵机有一个无限带，它被分成多个单元。
磁带符号出现在这些单元格中。
存在有限控制，它根据给定的输入控制图灵机的工作。
有限控件有一个读/写头，它指向磁带中的一个单元。
图灵机可以左右移动从一个单元格到另一个单元格。
输入和输出磁带符号
| …... | 乙 | X1 | X2 | … | 席 | ... | Xn | B | 乙 | ... |
↑
有限控制
图灵对输入可以有三种类型的动作。
打印 Si，向左移动一格 (L) 并进入状态 qj。
打印 Si，向右移动一格 (R) 并进入状态 qj。
打印 Si，不要移动 (N) 并转到状态 qj。