图灵机模型及数据编码

《图灵机模型及数据编码》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章图灵机模型及数据编码图灵机模型理论是计算学科最核心的理论之一图灵机模型为计算机设计指明了方向图灵机模型是算法分析和程序语言设计的基础理论。本章主要内容1.1图灵机1.2位的存储1.3存储器1.4数据在计算机中的表示1.5数据压缩1.6数据传输误码及对策图灵机的直观描述3个部件：有穷控制器、无穷带和读写头3个动作：改写当前格、左移或右移一格读写头有穷控制器存储带…………图灵机模型图灵机的形式化描述图灵机是一个五元组（K，∑，δ，s，H），其中：K是有穷个状态的集合；∑是字母表，即符号的集合；s∈K是初始状态；H∈K是停机状态的集合，当控制器内部状态为停机状态时图灵机结束计算；δ是转移

2、函数，即控制器的规则集合。计算“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）通用图灵机（1）编码方案：通用图灵机（2）通用图灵机蕴含的计算思想“x+1”图灵机功能是固定的，相当于一个程序通用的图灵机功能根据输入

3、编码的不同而变化程序也是数据存储程序和程序控制通用图灵机模型是计算机的计算能力的极限计算机系统应该有存储器（相当于存储带）、中央处理器（控制器及其状态），并且其字母表可以仅有0和1两个符号；为了能将数据保存到存储器并将计算结果从存储器送出来展示给用户，计算机系统还应该有输入设备和输出设备如键盘、鼠标、显示器和打印机等。1.2位的存储如果用0-1作为编码的基本元素的话，那么存储的最小单位为1位（bit），要么是0要么是1。可见只要存储装置有两种不同的稳定状态就能可以表示和存储这两个元素，其中一个状态表示1，则另一种状态就表示0逻辑运算门可以设计出进行逻辑运算的装置，比如用继电器或者齿轮等，

4、把这种能完成逻辑运算的装置称为门（Gate）。现代电子计算机中的门是用电子线路实现的，其中1和0分别用电平的高和低来表示。触发器其他存储技术磁芯电容磁介质有机玻璃或聚酯树酯等材料制作的介质1.3存储器1Byte＝8Bit1KB（kilobyte）＝1024Byte1MB（megabyte）＝1024KB1GB（gigabyte）＝1024MB1TB（terabyte）＝1024GB存储器主存储器地址辅助存储器软盘、硬盘和光盘等1.4数据在计算机中的表示二进制数值的表示字符的表示图形和图象的表示音频数据的表示数制进位计数的方法即数制在采用进位计数的数字系统中，如果只用r个数码，则称其为基r

5、数制（Radix-rNumberSystem）或r进制，r便称为该数制的“基数”（Radix）二进制：B（Binary），如(11101)B；八进制：O（Octal），如(35)O；十进制：D（Decimal），如(29)D；十六进制：H（Hexadecimal），如(1D)H；二进制与其他数制的转换（1）二进制与十进制的转换十进制转换成二进制：将整数部分和小数部分分别转换，然后再拼接起来整数部分，采用除2取余法；小数部分，采用乘2取整法。二进制转换为十进制：直接按权展开即可小数点后的权分别为2的-1、-2、-3、……次幂二进制与其他数制的转换（2）十进制转换成二进制：二进制与其他数制的

6、转换（3）二进制转换为十进制：二进制与其他数制的转换（4）二进制与十六进制的转换161＝24，4位二进制数刚好可以表示0－F这16个数码，也就是说二进制的4位数正好可以用1位十六进制数表示将二进制数10110101111011.011101转换为十六进制：(0010110101111011.01110100)B＝(2D7B.74)H将十六进制数2C1D.A1转换为二进制：(2C1D.A1)H＝(0010110000011101.10100001)B二进制与八进制的转换类似数值的表示（1）机器数把在机器内存放的正负号数码化的数称为机器数，把机器外部由正负表示的数称为真值数若一个数占8位，真

7、值数（－0101100）B的机器数为10101100数值的表示（2）整数和实数整数数值的表示（3）整数和实数实数数值的表示（4）若要考虑符号位的处理，则运算变得复杂:为了解决此类问题，在机器数中，负数有三种表示法：原码、反码和补码。数值的表示（5）原码：数符位以0表示正1表示负，数值部分就是绝对值的二进制表示，不便于加减运算反码：对于正数与原码相同；对于负数，数符位为1，其数值部分为绝对值取反补码：对于正数与原码相同；对于负数，数符