Relationships between Self-Testing/Correcting Programs and Interactive Proofs

即使是最简单的程序也可能充满难以捉摸的错误。 介绍了程序检查器、自测试程序和自校正程序的研究，以便允许人们使用程序P来计算函数f而不相信P正确工作。 许多问题很容易指定，但解决它们的高效程序可能非常复杂。 对于这样的问题，所提出的方法程序的正确性已经显示出承诺。 本项目的目标是了解这些技术的应用范围。 这项研究将开发一个核心的算法技术，用于编写快速和简单的检查器，自校正器和自测试器。 以前的研究自我校正和自我测试获得的理论工具和见解，已被用于在最近的结果在交互式证明系统的理论。 这项研究涉及这些领域之间的关系的研究。 在计算学习理论和博弈论领域的其他主题将进行研究。 这些主题应用于强化学习、文本校正、词性标记、DNA测序和手写识别中的算法。 互动活动包括教授一门名为程序正确性概率证明检查和互动证明的研究生课程。

Even the simplest of programs can be full of elusive errors. The study of program checkers, self-testing programs and self- correcting programs was introduced in order to allow one to use a program P to compute a function f without trusting that P works correctly. Many problems are easy to specify, but efficient programs which solve them may be vepy complicated. For such problems, the proposed approaches to program correctness have already show promise. The goal of this project is to understand how broadly these techniques apply. This research will develop a core of algorithmic techniques for writing fast and simple checkers, self-correctors, and self-testers. Previous research on self-correctors and self-testers obtained theoretical tools and insights which have been used in recent results in the theory of interactive proof systems. This research involves the study of the relationships between these areas. Other topics in the area of computational learning theory and game theory will be studied. These topics have applications to algorithms in reinforcement learning, text correction, part-of-speech-tagging, DNA sequencing and handwriting recognition. Interactive activities include teaching a graduate course entitled Program Correctness Probabilistic Proof Checking and Interactive Proofs.