北京大学Cousera学习笔记--2-计算导论与C语言基础-第一讲.计算机的基本原理-图灵机...
有限状态读写头从一个初始状态开始,对存储器上的输入数据进行读或写操作,经过有限步操作之后停机,此时存储器上的输出数据就是计算结果
(1) 图灵机的构成:
1、一条存储带:双向无限延长;上有一个个的小方格;每个小方格可存储一个数字、字母
2、一个控制器
《1》包含一个读写头,可以读、写、更改存储带上每个格的数字/字母
《2》可以接受设定好的程序语句
《3》可以存储当前自身的状态
《4》可以变换自身的状态
《5》可以沿着存储带一格一格地左移右移
(2) 图灵机运作机理
1、准备:
《1》存储带上符号初始化;
《2》控制器设置好自身当前状态;
《3》控制器置于起始位置
《4》准备好工作程序
2、反复执行以下工作直到停机
《1》读写头独处存储带上当前方格中的字母活数字
《2》根据自身当前状态和所读到的字符,找到相应的程序语句
《3》根据相应的程序语句,做三个动作
(1、在当前存储带方格上写入一个相应的字母或数字
(2、变更自身状态至新状态
(3、读写头向左或向右移一步
(3) 示例
当图灵机停机(死循环、不懂),表示计算完毕,表示当前存储带上保留的,是结算结果;停机意味着得出计算结果;
也就是说,对于一个问题的输入A,问:A能否推出B,如果能找到一个图灵机,得出对应的符号序列B,那么A到B就是可计算的,否则,该问题不可计算
(4) 图灵机的意义
1、给出了一个可实现的通用计算模型;
2、引入了通过“读写符号”和“状态改变”进行计算的思想;
3、证实了基于简单字母表完成复杂运算的能力;
4、引入了存储区、程序、控制器等概念的原型
疑问:图灵机的应用是怎么设计出来的,即控制器上的程序怎么写?