计算复杂性理论总结报告一、 图灵机(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是初始状态