第1章图灵机模型?图灵机模型理论是计算学科最核心的理论之一?图灵机模型为计算机设计指明了方向?图灵机模型是算法分析和程序语言设计的基础理论。本章主要内容?图灵机概述?计算“X+1”的图灵机?通用图灵机?图灵机模型的启示图灵机的直观描述?3个部件:有穷控制器、无穷带和读写头?3个动作:改写当前格、左移或右移一格读写头有穷控制器存储带…………图灵机模型图灵机的形式化描述?图灵机是一个五元组(K,∑,δ,s,H),其中:?K 是有穷个状态的集合;?∑是字母表,即符号的集合;?s ∈K是初始状态;?H∈K 是停机状态的集合,当控制器内部状态为停机状态时图灵机结束计算;?δ是转移函数,即控制器的规则集合。计算“x+1”的图灵机?目标:利用二进制来设计一个专门计算“x+1”的图灵机,要求计算完成时,读写头要回归原位?状态集合K:{start,add,carry,noncarry,overflow,return,halt};?字母表∑:{0,1,*};?初始状态s:start;?停机状态集合H:{halt};计算“x+1”的图灵机?规则集合δ:“5+1”的计算过程(1)“5+1”的计算过程(2)“5+1”的计算过程(3)“5+1”的计算过程(4)
图灵机模型 来自淘豆网m.daumloan.com转载请标明出处.
