图灵机模型

图灵机模型图灵机模型概论图灵机模型理论是计算学科最核心的理论之一图灵机模型为计算机设计指明了方向图灵机模型是算法分析和程序语言设计的基础理论。主要内容图灵机缘起图灵机描述计算“X+1”的图灵机通用图灵机图灵机模型的启示图灵机缘起1900,德国数学家希尔伯特提出23个数学难题中,逻辑的完备性问题,即是否所有数学问题原则上都可解.1936,英国数学家图灵“论可计算数及其在判定问题中的应用”(OnComputableNumbersWithanApplicationtotheEntscheidungsProblem)结论：可解的问题是能够用图灵机的自动机理论模型表达的问题.图灵机的直观描述3个部件：有穷控制器（有限状态机）、无穷带（符号集合）和读写头（读、改写、左移、右移）•3个动作：改写当前格、左移或右移一格•图灵机的计算：由控制器控制执行的一系列动作图灵机的形式化描述图灵机是一个五元组（K，∑，δ，s，H），其中：K是有穷个状态的集合；∑是字母表，即符号的集合；s∈K是初始状态；HK是停机状态的集合，当控制器内部状态为停机状态时图灵机结束计算；δ是转移函数，即控制器的规则集合。图灵机工作过程：计算“x+1”的图灵机目标利用二进制来设计一个专门计算“x+1”的图灵机，要求计算完成时，读写头要回归原位x由0、1串组成，“*”为x的分隔符、界定符状态集合K{start，add，carry，noncarry，overflow，return，halt}字母表∑{0，1，*}初始状态sstart；停机状态集合H{halt}；“x+1”图灵机规则集合（1）规则如果A那么B，形式化表示：AB•（控制器当前状态，读写头当前位置的符号）(读写头移动动作指示，读写头新位置的符号，控制器新状态)•图灵机控制器的规则：x+1”图灵机规则集合（2）规则集合δ：举例：“5＋1”的计算过程（1）初始状态根据规则集合δ：第一步完成后状态“5＋1”的计算过程（2）“5＋1”的计算过程（3）“5＋1”的计算过程（4）停机状态思考计算7+1的图灵机运算过程？通用图灵机图灵机本质在进行字符串的处理图灵机输入是一个字符串图灵机输出也是一个字符串如果将图灵机的有限内部状态与读写头的有限动作用字符串表示那么每条转换规则也可以用一个字符串表示（当前状态，当前符号，动作，新状态）图灵机可以由一个较长字符串完全表示通用图灵机通用图灵机实现“5+1”计算（1）编码方案通用图灵机实现“5+1”计算（2）3带通用图灵机M图灵机输入字符串：00100001000000010010（对应*100*）图灵机的所有规则，每个规则16位字符（当前状态，当前符号，动作，新状态）初始状态编码：0101（对应start状态)利用编码描述的规则：01010010001000110110通用图灵机实现计算的过程开始扫描第三条带获得当前状态S扫描第一条带获得当前符号C扫描第二条带查找规则串（Si，Ci，A，Sn）Si==SCi==C（Si，Ci，A，Sn）即转换规则（当前状态，当前符号，动作，新状态）否Si==结束状态？是否S=Sn根据A对第一条带执行相应动作是END发现什么？计算过程与具体的编码和规则都不相关！意味着什么？程序可以重复执行通用图灵机蕴含的计算思想（1）程序也是数据“x+1”图灵机功能是固定的，相当于一个程序通用的图灵机功能根据输入编码的不同而变化存储程序和程序控制M图灵机进一步展示了程序和其输入可以先保存到存储带上，M就按程序一步一步运行直到给出结果，结果也保存在存储带上。通用图灵机蕴含的计算思想（2）通用图灵机模型是计算机的计算能力的极限因为，根据丘奇-图灵论题：不能用图灵机完成的计算任务是不可计算的计算机系统应该有:存储器（相当于存储带）中央处理器（控制器及其状态），并且其字母表可以仅有0和1两个符号；为了能将数据保存到存储器并将计算结果从存储器送出来展示给用户，计算机系统还应该有输入设备和输出设备如键盘、鼠标、显示器和打印机等。通用图灵机蕴含的计算思想（3）通用图灵机的所有规则构成指令集指示指示了操作的对象（当前符号）指令指示了待实施的操作冯·诺依曼机对图灵机的实现1944年，冯·诺依曼参与ENIAC研究小组1945年,在ENIAC基础上，冯·诺依曼提出了EDVAC（ElectronicDiscreteVariableAutomaticCompUter)设计方案,计算机的组成包括：运算器、逻辑控制装置、存储器、输入和输出设备新的概念的提出随机读写(RandomAccess)随机读写存储器RAM(RandomAccessMemory)地址(Address)指令(Instruction)=操作码(OperatingCode,Opcode)+操作数(Operand)计算机指令系统精简指令集计算机复杂指令集计算机