Feasible Operations and Applicative Theories Based on λη (Q4511545)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1523410
Language Label Description Also known as
default for all languages
No label defined
    English
    Feasible Operations and Applicative Theories Based on λη
    scientific article; zbMATH DE number 1523410

      Statements

      0 references
      4 July 2001
      0 references
      applicative theories
      0 references
      polynomial time computability
      0 references
      asymmetric interpretation
      0 references
      Feasible Operations and Applicative Theories Based on λη (English)
      0 references
      The paper under review is centered around theories with self-application and their relationship to polynomial time computability. The central system of the paper is the theory \(\text{PTO}(\lambda\eta)\), which is essentially the system \(\text{PTO}^+\) introduced and analyzed by the reviewer [J. Symb. Logic 62, 575-594 (1997; Zbl 0891.03023)], augmented by the axioms of totality of application and extensionality of operations. Thus, \(\text{PTO}(\lambda\eta)\) is based on the ordinary lambda calculus with extensionality \(\lambda\eta\). The main achievement of the paper is a feasible asymmetric interpretation of \(\text{PTO}(\lambda\eta)\) into a suitable equational calculus, which in turn is based on the standard open term model of \(\text{PTO}(\lambda\eta)\). It is a crucial consequence of this interpretation that the provably total operations of \(\text{PTO}(\lambda\eta)\) on the type of binary words define exactly the polynomial time computable functions.
      0 references

      Identifiers