Mathematical Sciences: An Algebraic Measure of Computational Information Content

数学科学：计算信息内容的代数度量

• 批准号: 9625445
• 负责人: Manuel Lerman
• 金额: $ 6.3万
• 依托单位: University of Connecticut
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1996
• 资助国家: 美国
• 起止时间: 1996-08-01 至 2000-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9625445&HistoricalAwards=false
• 关键词: Mathematical; Sciences; Algebraic; Measure; Computational

DMS-9625445 PI: Manuel Lerman University of Connecticut Degree Theory analyzes the possible situations in which a program's oracle has the knowledge to predict how other specified oracles will act, through the use of an algebraic structure introduced by Post and Kleene fifty years ago. One of the main goals of Degree Theory has been to determine how closely this algebraic structure captures the notion of information content. In other words, there is a desire to determine whether oracles with different information content look different algebraically, or- if not- whether this inability to differentiate between two oracles is reflected in the algebraic structure in some more subtle way. The main tool for the study of the algebraic model of information content is the "priority method". Lerman is a co-developer of a framework which allows one to apply this technique in very general situations. The technique has not only been applied to study structural questions about information content, but has found applications to other areas of mathematical logic and computer science. Modern computing is interactive; programs pause frequently to ask for input from an oracle (the user) before continuing. Thus the true universal model for computing is one in which an oracle is appended to the computer. This project concerns the analysis of situations in which one oracle has the knowledge to predict how other specified oracles will act. Lerman is a co-developer of a framework which is used to analyze such programs, and is currently refining this framework to more easily determine whether such programs can be combined without producing conflicts. Insights obtained from the framework will apply to a range of situations involving computer programs with users who are providing input to the programs.

DMS-9625445 PI：康涅狄格州曼努埃尔·勒曼大学学位理论通过使用波斯特和克莱恩50年前引入的代数结构，分析了程序的先知具有预测其他指定先知将如何行动的知识的可能情况。度理论的主要目标之一是确定这种代数结构与信息内容的概念有多接近。换句话说，人们希望确定具有不同信息内容的先知在代数上是否看起来不同，或者-如果不是-这种无法区分两个先知的能力是否以某种更微妙的方式反映在代数结构中。研究信息内容的代数模型的主要工具是“优先方法”。Lerman是一个框架的联合开发人员，该框架允许人们在非常一般的情况下应用这项技术。这项技术不仅被应用于研究关于信息内容的结构性问题，而且还被应用于数理逻辑和计算机科学的其他领域。现代计算是交互式的；程序在继续之前经常暂停以请求Oracle(用户)输入。因此，真正的通用计算模型是将先知附加到计算机上的模型。这个项目涉及对情况的分析，在这种情况下，一个先知拥有预测其他指定先知将如何行动的知识。勒曼是一个用于分析这类程序的框架的联合开发者，目前正在完善这个框架，以更容易地确定是否可以在不产生冲突的情况下组合这些程序。从该框架获得的见解将适用于涉及计算机程序的一系列情况，用户向这些程序提供输入。