定义：图灵机是五元组(K, ∑, δ, s, H)，其中 K是状态的有穷集；∑是字母表，包含空格符和左端符，但不包含←和→，s∈K是初始状态，H⊆K是停机状态的集合，δ是转移函数，它是从(K-H)×∑到K×(∑∪{←, →})的函数，使得 (1)对所有q∈K-H，若δ(q,) = (p,b)，则b=→ (2)对所有q∈K-H和a∈∑，若δ(q,a)=(p,b)，则b≠
基本机器：
- 写符号机a
- 移带头机L和R
- 向右找第一个a：Ra
- 复制机C
定义：图灵机是五元组(K, ∑, δ, s, H)，其中 K是状态的有穷集；∑是字母表，包含空格符和左端符，但不包含←和→，s∈K是初始状态，H⊆K是停机状态的集合，δ是转移函数，它是从(K-H)×∑到K×(∑∪{←, →})的函数，使得 (1)对所有q∈K-H，若δ(q,) = (p,b)，则b=→ (2)对所有q∈K-H和a∈∑，若δ(q,a)=(p,b)，则b≠
基本机器：