译者序

<正> 由美国斯坦福研究院计算机科学实验室R. S. Boyer和J S. Moore博士合著、美国79年出版的《计算逻辑》一书,系统地介绍了当今计算机科学工作者十分关注并为之积极展开研究的课题——机械定理证明与程序正确性证明的形式化理论及其在计算机上实施的机械化方法。尤其是对人所共知、难度颇大的如何实现归纳法机械化的问题进行了卓有成效的研究,并给出了各式各     

新书介绍

<正> 由美国斯坦福研究院计算机科学实验室R. S. Boyer和J. S. Moore博士合著、于79年底美国出版的《计算逻辑》(A Computational Logic)一书,系统地介绍了当今计算机科学工作者十分关注并为之积极展开研究工作的课题——机械定理证明与程序正确性证明的形式化理论及其在计算机上实施的机械化方法。尤其是对人所共知、难度颇大的如何实现归纳法机械化的问题进行了卓有成效的研究,并给出了各式各样的实现技巧。全书分序、十九章正文及三个附录。第1章概说了该书的动机、形式理论及证明技术;     

一种证明程序正确性的方法

介绍一种证明程序正确性的方法,并和Floyed_Hoare公理学方法作了一些比较.为了形象的描述该方法,建立了一个抽象模型及一个程序实例,然后相对于这一模型并结合程序,给出了程序正确性的定义及其证明方法.     

计算机科学中的正确性问题

<正> 目前,遍及世界的计算机科学工作者正采用不同的途径研究程序正确性证明问题。为加强程序证明方面的工作,为表彰和鼓励那些在程序证明方面作出显著工作的杰出人材,美国最近专门设立了以著名计算机科学家、A.M.Turing奖获得者、LISP语言提出者John Mccarthy教授的名字命名的John Mccarthy奖。该奖1983年首次评奖,以后每两年评奖一次。经过评选,83年8月8日至12日在西德举行的第八次国际人工智能会议把首次Mccarthy奖授予在程序证明方面作出卓越成绩的美国奥斯丁得克萨斯大学计算机科学系Boyer和Moore博士。     

John Mccarty奖及其首次获奖者Boy-Moore

<正> 1.Mccarthy奖及其首次获奖者 随着计算机的高速发展和广泛应用,一些关键计算机软件中的程序隐患造成的耗费越来越大,消除这些程序隐患的呼声也愈来愈高。目前,遍及世界的计算机科学工作者正采用不同的途径研究程序正确性证明问题。许多程序证明专家(如荷兰技术大学的E.W.Dijkst-ra、英国爱丁堡大学的R.M.Burstall、以色列魏司曼学院的A.Pnueli、美国斯坦福大学的Z.Manna、美国斯坦福研究院的J.A.Go-guen、美国奥斯丁得克萨大学的R.S.Boy-er和J.S.Moore等)提出了这样的观点,即     

调试数据作为证明程序正确性的一种辅助手段

迄今为止,人们验证程序是否正确,无非是采用二种途径:证明和调试。程序正确性证明,理论上虽完美,但由于本身所具有的复杂性,对大型程序很难实现;程序调试做起来并不复杂,但由于调试实例的局限性,不能保证程序正确性。本文提出用调试数据帮助证明程序正确性,这对程序验证理论无疑是有意义的。     

一个不变式断言生成器

程序正确性证明是软件工程研究中一个很重要的课题。目前,程序正确性证明过程中一个最难解决的问题便是如何找出程序的不变式断言。本文在ELLOZY的基础上,对差分方程的化简公式进行讨论、简化,使得更方便、更有效地生成循环断言。我们在PDF—11机上用UCSD PASCAL语言实现了一个生成器,它能对含有数组的简单循环程序生成循环断言。     

基于Kripke结构的程序正确性证明

为了方便证明程序的正确性,引入了Kripke结构,提出基于Kripke结构的程序正确性证明。重新定义了适合证明的Kripke结构,并描述了将程序流程图转换为Kripke结构状态图的方法。给出了证明程序正确性的相关定理和基于Kripke结构的程序正确性证明方法。证明方法为:首先,把程序流程图转换为状态图;然后,根据状态之间的转移关系列出每个状态下的状态谓词;最后,证明每个状态谓词为真。根据状态谓词进行证明,能够反映出程序执行的状态。用该方法对一个实例进行了完整的证明。     

程序正确性证明的形式技术——J.Schwartz教授来华讲演记录

美国纽约大学柯朗数学科学研究所计算机科学部主任 J.Schwartz 教授,应中国科学院计算技术研究所邀请,于一九七七年九月十七日至十月三日偕夫人共同在京讲学。讲学内容之一为“程序正确性证明的形式技术”(Formal Techniques for Proof ofProgram Correctness),共分十讲,每讲约一小时半,写有提纲。要求听讲者事先阅读 Z.Manna 所著《计算的数学理论》(Mathematical Theory of Computation)。及 J.E.Rubin所著《数学家所用的集合论》(Set Theory for Mathematicians).临行前留下他本人所著《关于㊣程序的技术》(On correct-Program Technology)以及和M.Davis合著的《定理验证系统和证明校验系统的元数学可扩充性》(metamathematical Extensibility for Theorem Verifiers and Proof-Checkers).在证明程序正确性的研究中,有若干不同的算什么。其中之一是致力于研究保持程序正确性的加工(manispulation)和组合(Combination)规则,以便从一个正确的程序出发(例如,从一个则高级语言写成的,已被验证为正确的程序出发),经上述规则得到其他正确程序(如目标程序)。Schwartz教授认为这是一个重要的途径。他以SETL语言书写的程序为研究对象,并提出了接近于Hoare系统的形式化验证方法。他认为使用SETL高级语言,不但使程序编写得简短,而且在描述归纳断言(inductive assertion)方面也是自足的。Schwartz教授也研究了程序的加工和组合规则,称这为变形规则(transformation rule).另外,由于人工证明程序正确性的过程中,仍然难免错误,因这提出证明验证系统问题,即建立一个计算机化的系统,自动验证人们给出的证明是否正确,他介绍了自己和Davis在这方面的工作。Schwartz在京讲学期间,还作过两次大型讲演,内容之一为“程序设计的非确定型方法：用途及其实现”(Programming Nodeterminism:Use and implementation).因验证系统的程序语言中允许出现非确定的选择算子,故将讲演附在本文后一起发表。本文根据讲授提纲和听课笔记,并参照两篇专著于1977年底整理而成。其中第三部分变形的形式化由洛阳石油设计院陶志成负责整理,其余各部分则科学院计算所周巢尘整理。整理过程中得到唐稚松、吴允曾同志的关心和帮助。     

与程序正确性证明有关的当前研究动向

<正> 5.1 引言 关于程序正确性证明这一领域目前已进行了大量的研究。这里,为了便于讨论,我们把这些研究分成如下几方面: 1.关于证明(部分)正确性和终止的证明技术。 2.有关程序正确性的程序设计和语言设计的一些考虑。     

加强计算机本科专业程序正确性知识教育与能力培养

针对当前计算机本科专业对程序正确性的知识教育与能力培养十分薄弱,远不能满足未来计算机工作者的培养需求的情况,讨论程序正确性内涵及保障正确性的形式化方法的意义,分析计算机专业基础课程设置中存在的问题,提出加强正确性即形式化方法的知识教育与能力培养建议。     

基于断言的程序正确性检测工具

文章提出了程序断言检测工具设计方案和基于断言的程序正确性检测步骤.该工具的基本原理是Floyd提出的"用断言式方法"证明程序的正确性的方法,通过一个断言发现工兵从程序中发现该程序断言,然后与程序要求满足的断言条件比较,判明其正确性.该工具在复杂条件下对程序正确性判断和大量重复程序检测上能发挥重要的作用.     

一种基于程序正确性证明理论的程序开发方法

程序的形式推导方法是一种基于程序正确性证明理论的程序开发方法,它使得程序的开发和证明同时进行,程序开发完成的同时其正确性亦得以保 证,以两个问题的程序开发为例说明了程序的形式推导方法的使用。     

计算复杂性综述

这是作者荣获1982年度图灵奖时的讲演。在授奖会上评价他的成就时写道:“Cook 博士以他在计算机科学基础领域中有影响的成果而闻名。他在复杂性理论、计算的时空折衷、程序语言逻辑方面作了重大贡献。他的工作以优美而深刻为特征,启示了计算的内在本质”。这篇讲演综述了计算复杂性的历史发展,重点是关于定义一个问题的固有计算复杂性和证明问题复杂性上下界的基本结果,还讨论了概率计算和并行计算。     

计算机科学中的待解问题综述

本文从计算理论、人工智能基础和计算机系统等三方面阐述了计算机科学领域中的待解问题,其中任何一个问题的解决都会极大地推动计算机科学的发展。     

关于PASCAL语言处理符号公式的可行性

一、引言用计算机进行数学定理的证明,公式的推导,要求计算机应用心理学方法,模拟数学家的思维过程智能地求解问题。研究用计算机进行数学公式的推导称为计算机代数,它兴起于六十年代,七十年代渐趋形成计算机科学领域中最年轻的一个分支,而且显示出了它的巨大的生命力,广泛地应用于科学试验和理论研究中。     

基于良序集方法的程序终止性证明

在介绍程序正确性的定义和良序集的概念基础上,对良序集证明程序终止性思路和步骤进行了分析,利用实例来证明程序的终止性。     

基于分布计数的基数排序方法的研究

排序是计算机科学中一个非常重要的问题.提出了一种基于分布计数的基数排序方法,给出该算法定义、算法描述、算法正确性证明和算法分析;讨论了基于该排序算法几个关键问题的解决方法.算法理论分析和实验结果研究均表明该算法时间复杂度为O(N),速度优于快速排序,是一种高效的排序方法.     

计算机程序设计的公理基础

这篇文章对计算机程序设计的公理基础作了探索性说明;阐述了程序证明的部分公理和推理规则,并给出了实例;从理论和实践两个方面对采取公理方法证明程序和作形式语言定义可能得到的好处进行了全面评述。这篇文章在程序正确性证明或软件实现方面占有一定地位,自发表以来被广为引用,而且的确产生了许多可喜的结果。     

计算理论中的重大难题—P=？NP

计算理论研究各种计算模型、可计算性和计算的复杂性等计算的固有性质,是计算机科学理论研究的核心。可计算理论研究的基本问题是,什么是计算,什么是可计算和不可计算,它可以使我们精确地区分有算法的问题和没有算法的问题,从而可以在抽象意义上回答计算机究竟能干什么,不能干什么的问题。计算复杂性理论研究在可利用的空间和时