图灵机与现代计算机.ppt

目录 最早人们将机器的工作主要放到数学计算上 因而数学计算是焦点 图灵机就是一个逻辑的机器 解决的是 可计算性 的问题 图灵机的基本思想就是用机器来模拟人们用纸和笔进行数学运算的过程 图灵把这样的过程看作是两种简单的动作 即在纸上写上或擦除某个符号 把注意力从纸的一个位置移动到另一个位置 图灵机的概述 A Turing在1936年介绍了这样一个通用的计算模型 该模型具有以下两个性质该模型的每个过程都是有穷可描述的 过程必须是由离散的 可以机械执行的步骤组成 图灵机是计算机的一种简单数字模型 尽管简单 但它具有模拟通用计算机的计算能力 图灵机的概述 图灵机的基本模型 图灵机由一条两端可无限延长的带子 一个读写头以及一组控制读写头工作的命令组成 图灵机的工作原理 在一个图灵机的动作中 图灵机根据带头 读写头 所扫描的符号和有限控制器的状态可能作改变状态 在被扫描的带单元上重新写一个符号 以代替原来写在该单元上的符号 将带头向左或者右移一个单元 图灵机是一个五元组 K s H 其中 K是有穷个状态的集合 是字母表 即符号的集合 s K是初始状态 H K是停机状态的集合 当控制器内部状态为停机状态时图灵机结束计算 是转移函数 即控制器的规则集合 图灵机的形式化描述 现代计算机结构 现代计算机的发展 图灵机对计算机的影响 区别