283
edits
Pipe-calculus: Difference between revisions
→Variants and computational power
KalmanKeri (talk | contribs) (→Syntax) |
KalmanKeri (talk | contribs) |
||
| Line 61: | Line 61: | ||
=== Variants and computational power === | === Variants and computational power === | ||
The most basic variant of the calculus lacks any scoped constructs | The most basic variant of the calculus that lacks any scoped constructs is called '''zeroth-order''' as a reference to [[Wikipedia:Zeroth-order_logic|zeroth-order logic]]. | ||
Somewhat surprisingly, even the | Somewhat surprisingly, even the zeroth-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 e.g. with recursion or a stack. Determining the computational power of specific variants of the calculus is of interest. | 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 e.g. with recursion or a stack. Determining the computational power of specific variants of the calculus is of interest. | ||