Mathematical Sciences: An Algebraic Measure of Computational Information Content

DMS-9625445 PI：Manuel Lerman康涅狄格大学 度理论分析了可能的情况下，一个程序的预言机有知识来预测其他指定的预言机将如何行动，通过使用一个代数结构介绍了邮政和克莱因50年前。度理论的主要目标之一是确定这种代数结构如何紧密地捕捉信息内容的概念。换句话说，人们希望确定具有不同信息内容的神谕在代数上是否看起来不同，或者-如果不是-是否这种无法区分两个神谕的能力以某种更微妙的方式反映在代数结构中。 研究信息量代数模型的主要工具是“优先方法”。 Lerman是一个框架的联合开发者，该框架允许人们在非常一般的情况下应用这种技术。 该技术不仅应用于研究信息内容的结构问题，而且还应用于数理逻辑和计算机科学的其他领域。 现代计算是交互式的;程序在继续之前经常暂停以请求oracle（用户）的输入。 因此，真正的通用计算模型是一个附加在计算机上的预言。这个项目关注的情况下，其中一个预言家的知识，以预测其他指定的预言家将如何行动的分析。Lerman是一个用于分析此类程序的框架的共同开发者，目前正在改进该框架，以更容易地确定此类程序是否可以在不产生冲突的情况下组合。从框架中获得的见解将适用于一系列涉及计算机程序的情况，用户正在向程序提供输入。

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.