Repository logo
 

Theorem proving with the real numbers


No Thumbnail Available

Type

Thesis

Change log

Authors

Harrison, John Robert 

Abstract

This thesis discusses the use of the real numbers in theorem proving. Typically, theorem provers only support a few 'discrete' datatypes such as the natural numbers. However the availability of the real numbers opens up many interesting and important application areas, such as the verification of floating point hardware and hybrid systems. It also allows the formalization of many more branches of classical mathematics, which is particularly relevant for attempts to inject more rigour into computer algebra systems. Our work is conducted in a version of the HOL theorem prover. We describe the rigorous definitional construction of the real numbers, using a new version of Cantor's method, and the formalization of a significant portion of real analysis. We also describe . an advanced derived decision procedure for the 'Tarski subset' of real algebra as well as some more modest but practically useful tools for automating explicit calculations and routine linear arithmetic reasoning. Finally, we consider in more detail two interesting application areas. We discuss the desirability of combining the rigour of theorem provers with the power and convenience of computer algebra systems, and explain a method we have used in practice to achieve this. We then move on to the verification of floating point hardware. After a careful discussion of possible correctness specifications, we report on two case studies, one involving a transcendental function. We aim to show that a theory of real numbers is useful in practice and interesting in theory, and that the 'LCF style' of theorem proving is well suited to the kind of work we describe. As for verification applications, we hope to convince the reader that the verification of real industrial designs is well within the abilities of current theorem proving .technology.

Description

This thesis is not available on this repository until the author agrees to make it public. If you are the author of this thesis and would like to make your work openly available, please contact us: thesis@repository.cam.ac.uk.


Cambridge University Library can make a copy of this work available only for the purposes of private study and non-commercial research. Copies should not be shared or saved in any shared facilities. Copyright over the content of these works is with their authors. Theses from the Library collection are considered unpublished works and according to UK legislation quoting from them is not allowed without permission from their author.

If you can commit to these terms, please complete the request form which you can find through this link: https://imagingservices.lib.cam.ac.uk/


Please note that print copies of theses may be available for consultation in the Cambridge University Library's Manuscript reading room. Admission details are at http://www.lib.cam.ac.uk/collections/departments/manuscripts-university-archives

Date

Advisors

Keywords

Qualification

Doctor of Philosophy (PhD)

Awarding Institution

University of Cambridge