Mathematical Sciences: An Algebraic Measure of Computational Information Content

点击翻译按钮获取中文摘要

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.