计算模型 所谓计算模型是刻划计算这一概念的一种抽象的形式系统或数学系统，而算法是对计算过程步骤（或状态的一种刻划），是计算方法的一种能行实现方式。 由于观察计算的角度不同，产生了各种不同的计算模型，比如递归函数，图灵机，lambda函数等。 有趣的是，这些计算模型的计算能力被证明是等价的。 常用函数 加函数可以如下递归定义： f1(m,0)=m; f1(m,n+1)=s(m+n); 乘函数可以如下定义： f2(m,0)=z(m); f2(m,n+1)=f1(m,f2(m,n)); 减一函数可以如下定义： p(0)=0; p(n+1)=n; 常用的函数，都可以这样定义出来。 计算模型之二：图灵机 它由一个控制器和一条两端可无限延长的工作带组成： 工作带起着存储器的作用，它被划分为无穷多个可写可擦的方格。 控制器则可以在带上左右移动，控制带有一个读写头，读写头可以读出当前方格内的符号，然后根据预先设计的状态转换指令，选择改写或抹去这一符号，然后选择往左移一格，往右移一格或者不移动，并进入下一个状态。当状态转换到停机状态，则停止运行。 图灵可计算函数 可以在图灵机上构造实现的函数，称为图灵可计算函数。以下函数都是图灵可计算的，大家可以思考一下具体的构造过程。 自然数如何编码？ 零函数： 后继函数： 射影函数： 图灵机的计算能力等价于递归函数的计算能力 如何来证明递归可计算的函数，一定是图灵可计算的？ 三个初始函数是图灵可计算的。 三个算子形成的复合函数也是图灵可计算的。 如何来证明图灵可计算的函数，一定是递归可计算的？ 图灵机的优点 图灵机的计算能力与其他计算模型是等价的。 图灵机的优点是模拟人类的纸和笔的功能，比较符合人类对于“何为计算”的直观理解。 图灵机简洁的构造和运行原理隐含了存储程序的原始思想，深刻地揭示了现代通用电子数字计算机最核心的内容。 计算与计算机 由此可见，真正构成计算机科学基本的、核心的内容是围绕计算而展开的大量带有规律性的知识，而不是具体的实现技术。 因为，在将来，我们完全可能发展一种能表示二进制数及其运算的新技术，它比今天的微电子技术精度更高、生产价格更便宜。如果真是那样，这种技术就可能取代微电子技术在计算科学中的地位。 因此，我们常说，从这个意义上讲，软件技术比微电子技术对计算科学更重要一些。 * * 递归函数论是由厄布朗、哥德尔、克林等发展起来的计算理论。 三个初始函数： (1) s(x)＝x＋1 （后继函数）； (2) z(x)＝0 （零函数）； (3) Pj(n)(x1，x2，…，xn)＝xj （射影函数）。 三个算子：复合算子，递归算子，取极小算子。 由初始函数通过有限次使用算子可以构造的函数，称为递归函数。 计算模型之一：递归函数 控制器的命令可表示为： （状态，符号）→（写符号，移动，状态）； ┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬── │０│０│０│１│１│１│０│１│１│１│ ┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴── ↑ ┌─┐ │ │ ┌┘ └┐ │控制器│ └───┘ 输入：图灵机运行前，工作带上的内容就是输入。（输入之前用一个空格隔开，连续遇到两个空格表示结束） 输出：图灵机运行后进入结束状态，那么，图灵机就停机，此时带上的内容就是计算的输出结果。 例 M的字母表A＝{0，1，b}，b表示空格。状态集Q＝{q1，q2，q3}，其中，指定q1是开始状态，q3是终止状态。 M的程序（控制器的命令）如下： q1 0 1 R q1； q1 1 0 R q1； q1 b b R q2； q2 b b L q3； q2 0 0 H q1； q2 1 1 H q1； 我们可以画出对应的状态转换图，然后使用一些输入输出对，来判断该图灵机的功能。 也许是图灵机读写带上只出现两个符号启发了研究者，在当时的技术条件下，从便于元器件的设计和制造考虑，计算机的研制很自然地选择了二进制。后来的实践也证明了这种选择具有极大的优点。 十进制数的表示 例如，1997.630这个数可以写成： 1997.630＝1×103＋9×102＋9×101＋7×100 ＋6×10-1＋3×10-2＋0×10-3 二进制 一般地，任何一个十进制数S都可以表示为： S＝knkn-1 … k0.… k-m ＝kn×10n＋kn-1×10n-1＋…＋k0×100＋…＋k-m×10-m -m ＝ ∑ ki×10i i＝n 其中，10称为十进制的基,ki∈{0,1,2,3,4,5,6,7,8,9}，m，n为正整数。小数点的位置不言自明。 二进制和十进制一样，是一种数制，它用于表示数的符号（数字）由于在书写中的位置不同而具有不同的值。二进制表示数的符号只有两个，即0和1，其数值与十进制中的0和1相同。此外，与十进制不同之处在于二进制数是逢二进一。 例如，十进制数与二进制数中的一些可作如下对应： 十进制 二进制 (0) (0) (1) (1) (2) (10) (3) (11) (4) (100) (5) (101) … … … (9) (1001) (10) (1010) … … … 一般地，任何一个二进制数S都可以表示为： S＝knkn-1 … k0. … k-m ＝kn×2n＋kn-1×2n-1＋…＋k0×20＋…＋k-m×2-m ? -m ＝ ∑ ki×2i i＝n ? 其中，2称为二进制的基数，ki∈{0,1},m,n为正整数。 进一谈球吧步，读者可从十进制数和二进制数的一般表示公式得到启发，将这种表示推广到更一般的任意进制，不同之处只是基数不一样。 二进制的运算规则比十进制的运算规则简单得多。只要建立两种进制的数据之间的转换方法，那么，二进制将具有更多的优势。计算机的理论基础是逻辑和代数。当二进制与同样只使用“真”和“假”两个值的逻辑代数建立了联系后，这就为计算机的逻辑设计提供了便利的工具。 图灵机的带子可以看成是计算机的存储设备，数据可以存储在上面，也可以根据需要擦去。图灵机的命令相当于一组事先设计、存储好了的程序，它们在控制器安排下，决定读写头的每一步操作。这样一种数学机器，如果不考虑它的实用性，就思想和原理而言，确实包含了存储程序的重要思想。 图灵机诞生后不到十年，在以冯·诺依曼为代表的一批科学家的努力下，现代存储程序式电子数字计算机的基本结构与工作原理被确定下来。它主要由如下的五部分组成（见P25图）：存储器，运算器，控制器，输入设备，输出设备 计算模型的实现：存储程序式计算机 数字逻辑是数字电路逻辑设计的简称，其内容是应用数字电路进行数字系统逻辑设计。电子数字计算机是由具有各种逻辑功能的逻辑部件组成的，这些逻辑部件按其结构可分为组合逻辑电路和时序逻辑电路。组合逻辑电路是由与门、或门和非门等门电路组合形成的逻辑电路；时序逻辑电路是由触发器和门电路组成的具有记忆能力的逻辑电路。有了组合逻辑电路和时序逻辑电路，再进行合理的设计和安排，就可以表示和实现布尔代数的基本运算。而布尔代数只使用1（线（假）两个数，这样，当二进 数字逻辑与集成电路 制的加法、乘法等运算与布尔代数的运算建立了对应关系后，就可以用逻辑部件来实现二进制数据的加法、乘法等各种运算。 例 基本的“与”、“或”、“非”门电路。 “与”门电路一般有两个以上的输入和一个输出。图(a)表示了一个“与”门电路，其输出P和输入A、B、C之间的逻辑关系可用下面的式子表示： P＝A·B·C 电路设计中，用高电平信号表示1，低电平信号表示0，那么，“与”门电路只有当输入A、B、C同时为1时，输出P才为1，否则，P为0。 “或”门电路可以用图(b)表示。一般地说，“或”门电路是一种具有逻辑加法功能的电路，它有两个以上的输入和 一个输出，其输出P和输入A、B、C之间的逻辑关系可用下面的式子表示： P＝A＋B＋C 在具体的电路设计中，如果我们用高电平信号表示1，低电平信号表示0，那么，“或”门电路仅当输入A、B、C中有一个为1时，输出P就为1，否则，P为0。 “非”门电路可以用图(c)表示。一般地说，“非”门电路是一种具有逻辑取反功能的电路，它只有一个输入和一个输出，其输出P和输入A之间的逻辑关系可用下面的式子表示： P＝～A 在具体的电路设计中，如果我们用高电平信号表示1，低电平信号表示0，那么，“非”门电谈球吧路当输入A为0时，输出P就为1，否则，当输入A为1时，输出P为0。 “与”、“或”、“非”三种门电路示意图 P P P ↑ ↑ ↑ ┌──┻──┓ ┌──┻──┓ ┌──┻──┓ │ · │ │ ＋ │ │ ～ │ └┳─┳─┳┛ └┳─┳─┳┛ └──┳──┛ ↑ ↑ ↑ ↑ ↑ ↑ ↑ A B C A B C A ? （a） （b） （c） 将布尔代数和前面谈到的二进制联系起来，我们可以看出，“与”、“或”、“非”门电路的作用与集合运算“交”、“并”、“补”是一致的。一旦门电路中仅使用两个电平信号0和1，引入二进制及其运算规则，那么，用门电路及其组 合就可以实现二进制的各种运算，而对复杂电路的计算，如电路的化简就有可能通过布尔代数的方法进行。事实上也正是如此。
2、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
3、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
4、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
2024年退役军人职业技能大赛（无人机驾驶员）理论考试题库（含答案）.doc
2026年消防水泵房设备巡检记录表过程巡检版｜消防泵房/稳压泵/控制柜/试运行｜可填写清单台账模板｜Bloomprobe小样本B038.docx
2025年新九年级化学暑假提升讲义（沪教版）第15讲 化学反应发生的条件（原卷版）.pdf
DLT 5707-2014 电力工程电缆防火封堵施工工艺导则-行业标准.pdf
2025年新九年级化学暑假提升讲义（沪教版）第14讲 依据化学式的计算（原卷版）.pdf
原创力文档创建于2008年，本站为文档C2C交易模式，即用户上传的文档直接分享给其他用户（可下载、阅读），本站只是中间服务平台，本站所有文档下载所得的收益归上传人所有。原创力文档是网络服务平台方，若您的权利被侵害，请发链接和相关诉求至 电线) ，上传者
