1.1.1 图灵机

形式定义

一台图灵机是一个七元有序组 $M=<Q, \Gamma, b, \Sigma, \delta, q_0, F>$ ，其中：

$Q$ 是非空有穷状态(state)集合；
$\Gamma$ 是非空有穷带字母表(Tape alphabet)；
$b \in \Gamma$ 为空白符(blank symbol)，也是唯一允许出现无限次的字符；
$\Sigma\subseteq \Gamma\setminus \{b\}$ 是非空有穷输入字母表(input symbol)，初始时出现在带Tape上的内容；
$q_0 \in Q$ 是起始状态；
$F \subseteq Q$ 是终止状态(final state)或接受状态(accepted state)。初始时带上的内容是被 $M$ 接受的，当且仅当图灵机 $M$ 最终停在接受状态。
$\delta :(Q\setminus F) \times \Gamma \to Q\times \Gamma \times \{L,R\}$ 是转移函数(transition function)，其中 $L$ , $R$ 表示读写头是向左移还是向右移；它是一个部分函数(partial function)，换句话说对于某些状态 $q$ 和字符 $x$ ， $\delta(q,x)$ 可能没有定义，如果在运行中遇到没有定义的情况，机器将立刻停机。

除此外，还可显式地定义拒绝状态（rejected state），它是一种特殊的停机状态。原本 $\delta(q,x)$ 未定义会造成停机，那么也可以给它一个定义，使之转移到拒绝状态而停机。在这种情况下，图灵机有三种状态：接受，拒绝，永不停机。

还有一个不常见的变种，允许转移函数中除了左右移动，还可以保持原地不动，即在上面的定义中用 $\{L,R,N\}$ 代替 $\{L,R\}$ ，其中 $N$ 表示不移动(no shift, stay)。