Relationships between Self-Testing/Correcting Programs and Interactive Proofs

自检/纠错程序与交互式校样之间的关系

• 批准号: 9550380
• 负责人: Ronitt Rubinfeld
• 金额: $ 15.92万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1995
• 资助国家: 美国
• 起止时间: 1995-09-01 至 1996-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9550380&HistoricalAwards=false
• 关键词: Relationships; between; Self; Testing; Correcting

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.

即使是最简单的程序也可能充满难以捉摸的错误。 引入了对程序检查器，自我测试程序和自我纠正程序的研究，以便允许一个人使用程序p计算函数F而不相信P可以正常工作。 许多问题很容易指定，但是解决方案的有效程序可能会变得烦恼。 对于此类问题，提议的程序正确性方法已经显示出希望。 该项目的目的是了解这些技术的广泛应用。 这项研究将开发出算法技术的核心，用于编写快速，简单的检查器，自我校正和自我测试者。 先前关于自我校正和自我测试者的研究获得了理论工具和见解，这些工具和见解已在交互式证明系统理论中使用。 这项研究涉及研究这些领域之间的关系。 将研究计算学习理论和游戏理论领域的其他主题。 这些主题在增强学习，文本校正，标题部分，DNA测序和手写识别方面具有应用于算法。 互动活动包括教授题为“计划正确性概率证明检查和互动证明”的研究生课程。