This project is for basic research in the foundations of computing. The major emphasis is in the area of inductive inference, the capabilities and limitations of computers to learn by example. Several problems dealing with multiple machine inference, probabilistic inference, and the complexity of inference will be studied. The problem of inductive inference is related to the problem of program testing. The continued exportation of ideas and techniques from the field of inductive inference to applications concerning the testing of programs will be a main focus of this research. Other problems under study include foundational issues concerning data flow architectures and implementations of applicative programming languages. Issues and problems concerning abstract complexity theory have come out of the preliminary work of a previous NSF project. The fundamental problem addressed in this research is to classify and otherwise delimit the space of complexity measures that apply to a given programming system.
