Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. Classical Proofs as Programs: How, What and Why

Classical Proofs as Programs: How, What and Why

File(s)
91-1215.ps (334.29 KB)
91-1215.pdf (1.39 MB)
Permanent Link(s)
https://hdl.handle.net/1813/7055
Collections
Computer Science Technical Reports
Author
Murthy, Chetan R.
Abstract

We recapitulate Friedman's conservative extension result of(suitable) classical over constructive systems for $\Pi_{2}^{0}$sentences, viewing it in two lights: as a translation of programs from an almost-functional language (with $\cal C$) back to its functional core, and as a translation of a constructive logic for a functional language to a classical logic for an almost-functional language. We investigate the computational properties of the translation and of classical proofs and characterize the classical proofs which give constructions in concrete, computational terms, rather than logical terms. We characterize different versions of Friedman's translation as translating slightly different almost-functional languages to a functional language, thus giving a general method for arriving at a sound reduction semantics for an almost-functional language with a mixture of eager and lazy constructors and destructors, as well as integers, pairs, unions, etc. Finally, we describe how to use classical reasoning in a disciplined manner in giving classical (yet constructivizable) proofs of sentences of greater complexity than $\Pi_{2}^{0}$. This direction offers the possibility of applying classical reasoning to more general programming problems.

Date Issued
1991-07
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR91-1215
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance