TM

图灵机 (TM) 是一个 7 元组 $(Q,\Sigma ,\Gamma ,\delta ,q_0,q_a,q_r)$,

• $Q$ 是状态集;
• $\Sigma$ 是输入字母表, 不包括空白符;
• $\Gamma$ 是带字母表, 其中 $\text{空白符}\in \Gamma ,\Sigma \in \Gamma$.
• $\delta :Q\times \Gamma \to Q\times \Gamma \times \{L,R\}$ 是转移函数;
• $q_0\in Q$ 是起始状态;
• $q_a\in Q$ 是接受状态;
• $q_r\in Q$ 是拒绝状态, $q_a\ne q_r$.

图灵机根据转移函数运行.

• 若 TM 进入接受状态, 则停机且接受输入;
• 若 TM 进入拒绝状态, 则停机且拒绝输入;
• 否则 TM 一直运行不停机.

判定器

若图灵机 M 对所有输入都停机, 则称 M 为判定器.

指向原始笔记的链接

图灵可判定语言

某个 判定器 的语言称为图灵可判定语言.

指向原始笔记的链接

图灵可识别语言

某个图灵机的语言称为图灵可识别语言.

指向原始笔记的链接

NTM

非确定型图灵机 (NTM) 的转移函数为 $\delta :Q\times \Gamma \to P(Q\times \Gamma \times \{L,R\})$.

称 NTM M 接受 x, 若在 x 上运行 M 时有接受分支.

称 NTM 是判定的若对所有输入的所有分支都停机.

定理 每个 NTM 都有等价的确定 TM.

定理 每个判定 NTM 都有等价的判定 TM.

指向原始笔记的链接