Turing机
Turing机由以下内容构成
$1.\quad$无限长格带，每个格子状态为空或者为有限集合$\{a_1,a_2,\cdots,a_k\}$中的一种，称此集合为字母表
$2.\quad$控制单元，其状态为有限集合$\{s_1,s_2,\cdots,s_l,H\}$中的一种，其中$H$为中止态，当控制单元处于中止态则停止计算，称此集合为内部状态
$3.\quad$读写头，其每次读取和改变格带中一个格子的状态，当完成读写后，读写头左移或右移一格，或者中止计算
Turing机的一次计算即为读写头将一格和控制单元改变为新的状态，然后左移或右移一格或者中止计算，可用以下映射来表示，其中 $d=l,r,-$ 分别表示左移、右移和中止
$$f:(s,a)\mapsto (\bar s,\bar a,d)$$
通过特定状态集和映射函数可以让Turing机完成特定计算任务，称为专用Turing机
加法Turing机
所需字母表和内部状态分别为$A=\{1\}，S=\{s_1,s_2,s_3,s_4,H\}$，格子为空用$b$表示，所需计算的相加数字采用一元表示，即 $1=1,2=11,3=111,\cdots$，以下格带表示计算 $2+3$ 的格带初始状态，箭头为读写头初始位置和状态
$$\cdots|b|b|1|1|b|1|1|1|\overset{\overset{s_1}{\downarrow}}{b}|b|\cdots$$
实现加法所需的映射函数如下
$$$$
| $s$ | $a$ | $\bar s$ | $\bar a$ | $d$ |
|---|---|---|---|---|
| $s_1$ | $b$ | $s_2$ | $b$ | $l$ |
| $s_2$ | $b$ | $s_3$ | $b$ | $l$ |
| $s_2$ | $1$ | $s_2$ | $1$ | $l$ |
| $s_3$ | $b$ | $H$ | $b$ | $-$ |
| $s_3$ | $1$ | $s_4$ | $b$ | $r$ |
| $s_4$ | $b$ | $s_2$ | $1$ | $l$ |