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
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
0.7719911336898804
0 references
0.7699890732765198
0 references
0.7699890732765198
0 references
0.7242323756217957
0 references
0.7042532563209534
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