计算复杂性理论总结报告一、 图灵机（1） 图灵机基本模型图灵机是由图灵（Alan Mathisom Turing）在1936年提出的，它是一个通用的计算模型。通过图灵机，来研究递归可枚举集和部分递归函数，对算法和可计算性进行研究提供了形式化描述工具。图灵机的基本模型包括一个有穷控制器，一条含有无数个带方格的输入带和一个读写头。其直观物理模型如下图1所示。基本图灵动作有以下三种：（1） 改写被扫描带方格内容，控制器转化为下一状态。（2） 读写头向左移一个带方格，控制器转化为下一状态。（3） 读写头向左移一个带方格，控制器转化为下一状态。图1图灵机（2） 图灵机形式化定义，图灵机演算过程及语言描述定义：一个基本图灵机定义为一个七元组 TM=Q,C,A,B,q1,F。其中Q是状态集合，（图灵机所有的状态）非空有限集；C是带符号表，（放在带方格中的符号集合）非空集；是控制函数或过程转换函数（定义控制器）：QxCQxC（R,L）； A是输入字母表，AC； B是空白符，BC； q1是初始状态
