图灵机模型PPT讲座.ppt

图灵机模型概论图灵机模型理论是计算学科最核心的理论之一图灵机模型为计算机设计指明了方向图灵机模型是算法分析和程序语言设计的基础理论。主要内容图灵机缘起图灵机描述计算“X+1”的图灵机通用图灵机图灵机模型的启示图灵机缘起1900,德国数学家希尔伯特提出"23个数学难题"中,逻辑的完备性问题,,英国数学家图灵“论可计算数及其在判定问题中的应用”(putableNumbersWithanApplicationtotheEntscheidungsProblem)结论:可解的问题是能够用"图灵机":有穷控制器(有限状态机)、无穷带(符号集合)和读写头(读、改写、左移、右移)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)