283
edits
Pipe-calculus: Difference between revisions
→Variants
KalmanKeri (talk | contribs) |
KalmanKeri (talk | contribs) |
||
| Line 23: | Line 23: | ||
* Untyped lambda calculus can be translated to a subset of higher-order pipe-calculus. | * Untyped lambda calculus can be translated to a subset of higher-order pipe-calculus. | ||
=== Variants === | === Variants and computational power === | ||
Pipe-calculus is meant to be an extensible framework. An important extension is the inclusion of variables. | Pipe-calculus is meant to be an extensible framework. An important extension is the inclusion of variables. | ||
| Line 29: | Line 29: | ||
The most simple variant of the calculus that is lacking variables and scoped constructs is called '''zero-order'''. | The most simple variant of the calculus that is lacking variables and scoped constructs is called '''zero-order'''. | ||
Somewhat surprisingly, even the zero-order calculus has a limited computational power. | Somewhat surprisingly, even the zero-order calculus has a limited computational power. | ||
In the '''higher-order''' calculus there are lexically scoped variables that can bind arbitrary terms. Intermediate variants can be constructed by extending the basic calculus with recursion and with a stack. | In the '''higher-order''' calculus there are lexically scoped variables that can bind arbitrary terms. Intermediate variants can be constructed by extending the basic calculus with recursion and with a stack. Clarifying the computational power of specific variants of the calculus is also an ongoing effort. | ||
== Zero-order calculus == | == Zero-order calculus == | ||