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. The Computational Behaviour of Girard's Paradox

The Computational Behaviour of Girard's Paradox

File(s)
87-820.ps (316.72 KB)
87-820.pdf (1.51 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6660
Collections
Computer Science Technical Reports
Author
Howe, Douglas J.
Abstract

In their paper "Type" Is Not a Type, Meyer and Reinhold argued that serious pathologies can result when a type of all types is added to a programing language with dependent types. Central to their argument is the claim that by following the proof of Girard's paradox it is possible to construct in their calculus $\lambda^{\tau \tau}$ a term having a fixed-point property. Because of the tremendous amount of formal detail involved, they were unable to establish this claim. We have made use of the Nuprl proof development system in constructing a formal proof of Girard's paradox and analysing the resulting term. We can show that the term does not have the desired fixed-point property, but does have a weaker form of it that is sufficient to establish some of the results of Meyer and Reinhold. We believe that the method used here is in itself of some interest, representing a new kind of application of a computer to a problem in symbolic logic.

Date Issued
1987-03
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR87-820
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

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