AUTOMATING REASONING IN AN IMPLEMENTATION OF CONSTRUCTIVE TYPE THEORY.

摘要

The starting point for this thesis is the Nuprl proof development system. Nuprl is an environment for the development of formal computational mathematics that has as a logical basis a rich constructive type theory.;The second contribution is the use of Nuprl to solve an open problem in the theory of programming languages. The set of basic tactics together with various tools provided by Nuprl played a crucial role in the solution, and it seems that this problem is not tractable without computer assistance.;The third contribution is the construction in Nuprl of a kind of reflection mechanism that allows the use of Nuprl's type theory as a language for tactic programming. The main part of this work consists of a formal development within Nuprl of what may be regarded as the beginning of a new kind of book. It is a computerized development and explanation of a useful partial reflection of Nuprl within itself. Developments of formal mathematics that have this library as a base will be able to incorporate facts that are usually considered metamathematical, such as theorems about the correctness of algorithms for establishing mathematical facts. Such theorems allow subsequent uses of the corresponding algorithms. As an application, a formally verified term-rewriting system is constructed.;The work presented in this thesis concerns the automation of reasoning in Nuprl, and consists of three contributions. The first is a collection of basic tactics that can aid formal reasoning in a variety of domains. These tactics are simple enough that their function can be readily understood, yet powerful enough to permit the development of significant formal mathematics.