计算机科学逻辑基础

《计算机科学逻辑基础》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维普资讯http://www.cqvip.com第15卷第3期扬州师院学报(自然科学版)Voll5,No3I995年9月JouraalofYan~houTeachersColle辩aturalSciencescDt．1995计算机科学的逻辑基础一rP，DI张宏裕(薮莩事讦舅机秆擘系)A擒耍对敷理逻辑在计算机科学发展过程中的作用进行了评述．指出可计算性理论圈灵机数学模型为电子数字计算机的发明奠定了基础：开关电路、时序电路、自动机是网络理论的应用与发展；计算复杂性是递归论的具体应用；形式语言是一阶逻辑的深化：程序正确性证明中应用了模态逻辑；Her

2、brand定理和范式定理是机器证明的理论基础关蕾词壁，墅塑数理逻璃中圈法分类号TP302．21数理逻辑为现代电子数字计算机的发明奠定了理论基础本世纪30年代，Gfdel在证明形式化算术系统的不完全性定理时．建立了一系列原始递归函敷，经Kleene的发展而形成递归函数理论．1936年，Church定义了卜演算，Turing定义了理想计算机——图灵机，发展了可计算函敷理论．可以证明以上几种理论是相互等价的．Church还提出一个著名的论题(thesis)：直观上能行可计算函数类与经过严格敷学定义的可计算函敷类是相等的．这些理论成果为计算机的发明作

3、好了思想准备．’尉图圈灵机Turing设计了一架理想机，一个经严格敷学方法定义的可计算模型，人们称它为图灵机．它有一两端可以无限伸长的纸带，上面分成小方格，有一个读写头。用来识别正在被读写头注视(扫描)的方格中的符号(如附图所示)，还可在正注视的空白方格中写人符号或擦去已有符号，并可以左右移动．图灵机还有有穷多个内部状态。体现存储功能．在给定时刻的下一步运算由当时内部状态和正扫描的方格中已知符号所决定．这样，已知出现在所扫描的方格中的符号，内部状态的唯一功能是确定下一步动作．而下一步动作为下列几种类型之-：1)停止计算：2)对出现在正扫描方格

4、内的符号作一次特定的改变：3)向正扫描的方格右移一格或左移一格，随即内部状态作一次改变．内部状态由一组规则决定，这组规则能够从机器所能印刷的每一个符号确定下一步动作最们可以把上述思想进行严格的敷学定义，现略述如下：本文于1995年5月8B收到．江苏省教蛋自然科学基金贷时谭题维普资讯http://www.cqvip.com第3期张宏裕：计算机科学的逻辑基础以q．．。⋯．．表示内部状态，S。。S．。⋯．S表示机器所能印刷的符号，称．为字母表，L，R表示读写头左右移．从。⋯，．，S。，S．，⋯·S·R，L中选取的．．一个有穷符号序列称为表达式．一个

5、四元组是下列表达式之一：S，Sq，，，SRqI，S，Lq．，qS．q．．图灵机是四元组韵非空集。若它有二四元组且其前面两个元索是相同的，则称它为不确定的图灵机。否则，为确定的．不含qSq，类型四元组的图灵机称为简单的．敦在纸带上的表示方法如下：敦在输入时。用连续+1)个1表示之，记为字母表中以S表示l，为写人数组。字母表中有符号表示空白。于是敦组(2。3。4)可表示为(2'3'—4)一(j，j。)：(IlIB]I1]BIIll】)．输出则约定为停机后纸带上出现的l的个数．给定一函数』若用图灵机计算它，则需要有针对性地具体设计出一个四元组的有穷

6、集来．图灵机的运算步骤，由瞬时描述来刻画．瞬时描述为一表达式，它包含一个q。不含。L_且q，不是最右的符号．由ct到ot的转换是运用一次四元组来实现的，可记为ot—ot．已知函数Ix)(为简单起见，只就一元函数说明)，自变元值^。设计了图灵机z，如)定义§存在瞬时插述序列(程序)。，⋯，，使得。一．+．(0≤

7、579Il13⋯S对应4+7。q对应4i+5．对应敦称为该符号的哥德尔敦，表达式M—r．，⋯，r．的哥德尔敦r—rl；。，pr(k)一Xn(M)，其中n‘为r的哥德尔数。pr(k)为第k个质数。程序P一<。，⋯，．>的哥德尔数e=兀：．．)．这样，我们可称e为P的指标，有指标e的程序记为，．。，．计算的函鼓记为．．自然，一函数可以有多个程序计算它．用哥德尔编码方法把图灵机算术化了。是可计算性理论导出深刻结果的根本原因．有了可计算函数，可以用它作谓词(关系)的特征函数，从而把讨论扩充到谓词上．有一类谓词称为可判定时。即在有穷步以内能判定其真还是

8、假．一个著名的停机问题不可判定，即哥德尔敦为x的程序，，在输人为时，，)的值能不能算出来，是没有一般方法判断出来的．这一结果告诫我们。不存在诊断程序是否陷入死循环的