3.2 Variants of Turing Machines

各种TM的变种跟原生的single-tape TM是等价的

• Multitape Turing Machines
• Nondeterministic Turing Machines
• 双向无穷带
• 多维带
• 多头

计算装置的工作方式

识别器：输入$w$，输出0/1/?

判别器：输入$w$，输出0/1

转换器：输入$w$，输出$y$

产生器：输入$0^n$，输出$y_n$

枚举器：输入$\epsilon$，输出$y_1,y_2,...$

​ 无遗漏、无多余（可重复）、无顺序