New Directions in Program Checking

这个项目将研究程序检查的概念， 是一种在程序输出中获得信心的技术。 的 程序检查的传统替代方案是程序验证， 这是很难做到的，而程序测试， 数学保证 程序检查打击健康 妥协--为一个问题设计一个检查器， 设计一个算法，但检查提供精确的 保证输出的正确性。 其中一个主要的目标将是设计跳棋的问题， 目前都是由未经证实的化学方法解决的。 此外，效率和 实际检查员将实施的问题，在科学 计算，特别强调检查软件包， 线性规划，线性代数中的问题，以及普通和 偏微分方程 这项研究的另一个主要目的是探索 对有关的新结果的程序检查的影响 交互式证明和随机自归约的概念。 之间 这里考虑的问题是， 问题是检查。 编写检查程序作为软件设计的一部分可能成为标准 实践在不久的将来，这项研究旨在了解 程序检查的基础。//

This project will investigate the concept of program checking, which is a technique for gaining confidence in the output of a program. The traditional alternatives to program checking are program verification, which is hard to do, and program testing, which does not provide mathematical guarantees. Program checking strikes a healthy compromise--designing a checker for a problem is only as difficult as designing an algorithm for it, but checking provides precise guarantees about output correctness. One of the major goals will be to design checkers for problems which are currently solved by unproven heuristics. Also, efficient and practical checkers will be implemented for problems in scientific computing, with special emphasis on checking software packages for linear programming, problems in linear algebra, and ordinary and partial differential equations. The other major thrust of this research will be to explore the implications to program checking of new results on the related concepts of interactive proofs and random self reducibility. Among the questions considered here will be whether the satisfiability problem is checkable. Writing a checker as part of designing software may become standard practice in the near future, and this research aims to understand the foundations of program checking.//