计算机科学的逻辑基础.pdfVIP

  1. 1、本文档共8页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
维普资讯 第15卷 第3期 扬州师院学报 (自然科学版) Voll5,No 3 I995年 9月 JouraalofYan~hou TeachersColle辩 aturalScience scDt.1995 计 算机科 学 的逻辑基 础 一 rP,DI 张 宏 裕 (薮莩事讦舅机秆擘系) A 擒耍 对敷理逻辑在计算机科学发展过程中的作用进行了评述.指出可计算性理论 圈灵机数学模型 为电子数字计算机的发明奠定 了基础 :开关电路、时序 电路、 自动机是 网络理论 的应用与发展;计算复 杂性是递归论的具体应用;形式语言是一阶逻辑 的深化:程序正确性证明中应用了模态逻辑;Herbrand 定理和范式定理是机器证明的理论基础 关蕾词 壁 ,墅 塑 数理逻璃 中圈法分类号 TP302.2 1 数理逻辑为现代电子数字计算机的发明奠定了理论基础 本世纪 30年代,Gfdel在证明形式化算术系统的不完全性定理时.建立了一系列原始递 归函敷,经 Kleene的发展而形成递归函数理论.1936年,Church定义了 卜演算,Turing定 义了理想计算机——图灵机,发展了可计算函敷理论.可以证明以上几种理论是相互等价的. hCurch还提出一个著名的论题(thesis):直观上能行可计算函数类与经过严格敷学定义的可计算 函敷类是相等的.这些理论成果为计算机的发明作好了思想准备. ’ 尉 图 圈灵机 Turing设计 了一架理想机,一个经严格敷学方法定义的可计算模型,人们称它为图灵机. 它有一两端可以无限伸长的纸带,上面分成小方格,有一个读写头。用来识别正在被读写头 注视(扫描)的方格中的符号(如附图所示),还可在正注视的空 白方格中写人符号或擦去已有符 号,并可以左右移动.图灵机还有有穷多个内部状态。体现存储功能.在给定时刻的下一步运算 由当时内部状态和正扫描的方格中已知符号所决定.这样,已知出现在所扫描的方格中的符 号,内部状态的唯一功能是确定下一步动作.而下一步动作为下列几种类型之--:1)停止计 算:2)对出现在正扫描方格 内的符号作一次特定的改变:3) 向正扫描的方格右移一格或左 移一格,随即内部状态作一次改变.内部状态由一组规则决定,这组规则能够从机器所能印刷 的每一个符号确定下一步动作最们可以把上述思想进行严格的敷学定义,现略述如下: 本文于 1995年 5月 8B收到. 江苏省教蛋自然科学基金贷时谭题 维普资讯 第 3期 张宏裕:计算机科学的逻辑基础 以q.. 。…. . 表示 内部状态,S。。S.。….S 表示机器所能印刷的符号,称 . 为字母表,L,R表示读写头左右移 .从 。…, ., S。, S.,… ·S · R,L中选取的 . . 一 个有穷符号序列称为表达式 .一个 四元组是下列表达式之一: S,S q,, ,SRqI, S,Lq.,qS.q ..图灵机是四元组韵非空集 。若它有二四元组且其前面两个元索是相同 的,则称它为不确定的图灵机。否则,为确定的 .不含 qSq ,类型四元组的图灵机称为简 单的.敦在纸带上的表示方法如下 :敦 在输入时。用连续 +1)个 1表示之,记为 字母 表 中以S 表示 l,为写人数组。字母表 中有符号 表示空白。于

您可能关注的文档

文档评论(0)

***** + 关注
实名认证
文档贡献者

本账号下所有文档分享可拿50%收益 欢迎分享

1亿VIP精品文档

相关文档