Prove or disprove the Barendregt–Geuvers–Klop conjecture.
(more unsolved problems in computer science)
In the branches of mathematical logic known as proof theory and type theory, a pure type system (PTS), previously known as a generalized type system (GTS), is a form of typed lambda calculus that allows an arbitrary number of sorts and dependencies between any of these. The framework can be seen as a generalisation of Barendregt's lambda cube, in the sense that all corners of the cube can be represented as instances of a PTS with just two sorts.[1][2] In fact, Barendregt (1991) framed his cube in this setting.[3] Pure type systems may obscure the distinction between types and terms and collapse the type hierarchy, as is the case with the calculus of constructions, but this is not generally the case, e.g. the simply typed lambda calculus allows only terms to depend on terms.
Pure type systems were independently introduced by Stefano Berardi (1988) and Jan Terlouw (1989).[1][2] Barendregt discussed them at length in his subsequent papers.[4] In his PhD thesis,[5] Berardi defined a cube of constructive logics akin to the lambda cube (these specifications are non-dependent). A modification of this cube was later called the L-cube by Herman Geuvers, who in his PhD thesis extended the Curry–Howard correspondence to this setting.[6] Based on these ideas, G. Barthe and others defined classical pure type systems (CPTS) by adding a double negation operator.[7]
Similarly, in 1998, Tijn Borghuis introduced modal pure type systems (MPTS).[8] Roorda has discussed the application of pure type systems to functional programming; and Roorda and Jeuring have proposed a programming language based on pure type systems.[9]
The systems from the lambda cube are all known to be strongly normalizing. Pure type systems in general need not be, for example System U from Girard's paradox is not. (Roughly speaking, Girard found pure systems in which one can express the sentence "the types form a type".) Furthermore, all known examples of pure type systems that are not strongly normalizing are not even (weakly) normalizing: they contain expressions that do not have normal forms, just like the untyped lambda calculus[citation needed]. It is a major open problem in the field whether this is always the case, i.e. whether a (weakly) normalizing PTS always has the strong normalization property. This is known as the Barendregt–Geuvers–Klop conjecture[10] (named after Henk Barendregt, Herman Geuvers, and Jan Willem Klop).
^ abPierce, Benjamin (2002). Types and Programming Languages. MIT Press. p. 466. ISBN 0-262-16209-1.
^ abKamareddine, Fairouz D.; Laan, Twan; Nederpelt, Rob P. (2004). "Section 4c: Pure type systems". A modern perspective on type theory: from its origins until today. Springer. p. 116. ISBN 1-4020-2334-0.
^Barendregt, H. P. (1991). "Introduction to generalized type systems". Journal of Functional Programming. 1 (2): 125–154. doi:10.1017/s0956796800020025. hdl:2066/17240. S2CID 44757552.
^Barendregt, H. (1992). "Lambda calculi with types". In Abramsky, S.; Gabbay, D.; Maibaum, T. (eds.). Handbook of Logic in Computer Science. Oxford Science Publications.
^Berardi, S. (1990). Type dependence and Constructive Mathematics (PhD thesis). University of Torino.
^Geuvers, H. (1993). Logics and Type Systems (PhD thesis). University of Nijmegen. CiteSeerX 10.1.1.56.7045.
^Barthe, G.; Hatcliff, J.; Sørensen, M. H. (1997). "A Notion of Classical Pure Type System". Electronic Notes in Theoretical Computer Science. 6: 4–59. CiteSeerX 10.1.1.32.1371. doi:10.1016/S1571-0661(05)80170-7.
^Borghuis, Tijn (1998). "Modal Pure Type Systems". Journal of Logic, Language and Information. 7 (3): 265–296. doi:10.1023/A:1008254612284. S2CID 5067584.
^Jan-Willem Roorda; Johan Jeuring. "Pure Type Systems for Functional Programming". Archived from the original on 2011-10-02. Retrieved 2010-08-29. Roorda's masters' thesis (linked from the cited page) also contains a general introduction to pure type systems.
^Sørensen, Morten Heine; Urzyczyn, Paweł (2006). "Pure type systems and the lambda cube § 14.7". Lectures on the Curry–Howard isomorphism. Elsevier. p. 358. ISBN 0-444-52077-5.
as proof theory and type theory, a puretypesystem (PTS), previously known as a generalized typesystem (GTS), is a form of typed lambda calculus that...
with a type of all types (Type : Type) is not normalizing due to Girard's paradox. This system is also the simplest puretypesystem, a formalism which...
of typedsystem. The λ-cube can be generalized into the concept of a puretypesystem. The simplest system found in the λ-cube is the simply typed lambda...
PureSystems is an IBM product line of factory pre-configured components and servers also being referred to as an "Expert Integrated System". The centrepiece...
science, a type theory is the formal presentation of a specific typesystem. Type theory is the academic study of typesystems. Some type theories serve...
dependent type is a type whose definition depends on a value. It is an overlapping feature of type theory and typesystems. In intuitionistic type theory...
stamp, metadata in MPEG video or other streams Pseudoterminal slave Puretypesystem in mathematical logic PTS (amphibious vehicle), a Soviet vehicle Probability...
national governments and subsidiary organizations. The main types of modern political systems recognized are democracies, totalitarian regimes, and, sitting...
The Critique of Pure Reason (German: Kritik der reinen Vernunft; 1781; second edition 1787) is a book by the German philosopher Immanuel Kant, in which...
spatial coordinates of an electron. Preparing a system by measuring the complete set of compatible produces a pure quantum state. More common, incomplete preparation...
of the features of the typesystems and type checking of multiple programming languages. Brief definitions A nominal typesystem means that the language...
Ideal type (German: Idealtypus), also known as puretype, is a typological term most closely associated with the sociologist Max Weber (1864–1920). For...
Economic Systems: A Political-Economic Approach. Harcourt College Publishing. pp. 6–7. ISBN 978-0-15-512403-5. Pure capitalism is defined as a system wherein...
extensionality and proof irrelevance. Puretypesystem Lambda cube System F Dependent type Intuitionistic type theory Homotopy type theory Calculus of Inductive...
language. Writing systems can generally be classified according to how symbols function according to these rules, with the most common types being alphabets...
Pure Land Buddhism or Pure Land School (Chinese: 淨土宗; pinyin: Jìngtǔzōng; Japanese: 浄土仏教, romanized: Jōdo bukkyō; Korean: 정토종; RR: Jeongto-jong; Vietnamese:...
treats all functions as deterministic mathematical functions, or pure functions. When a pure function is called with some given arguments, it will always...
conventionally. A mathematical symbol is a type of ideogram. As true writing systems emerged from systems of pure ideograms, later societies with phonetic...
monoclinic crystal system is one of the seven crystal systems. A crystal system is described by three vectors. In the monoclinic system, the crystal is described...
psychology to biology by using pure logic. Numerous psychologists, including Carl Jung and Sigmund Freud developed systems that logically organize psychological...
proposed, including a wider range of power levels (Types 0, IV, and V) and the use of metrics other than pure power (e.g., computational growth or food consumption)...
design types: pure fission weapons are the simplest, least technically demanding, were the first nuclear weapons built, and so far the only type ever used...
Great American Pure Flix, formerly Pure Flix and sometimes stylized as Pureflix, is an American Christian media subscription over-the-top streaming service...
to the declared type of the pointer or reference, or "late" (i.e., by the runtime system of the language), according to the actual type of the object is...
implemented to support EFI. To differentiate the EFI file system from pure FAT, a new partition file systemtype has been defined. "Technical Note TN2166: Secrets...
diffusion to pure platinum leg as well as from Rhodium volatilization. This type has the same uses as type S, but is not interchangeable with it. Type S (90%Pt/10%Rh–Pt...
Global Information