283
edits
Pipe-calculus: Difference between revisions
→Variants and computational power
KalmanKeri (talk | contribs) No edit summary |
KalmanKeri (talk | contribs) |
||
| Line 60: | Line 60: | ||
=== Variants and computational power === | === Variants and computational power === | ||
In pipe-calculus Turing-completeness is not a starting point but a destination, and the intermediate steps are also worth inspection. In certain lines of research processes represent types<ref>Hans Hüttel et al.: [https://dl.acm.org/doi/pdf/10.1145/2873052 Foundations of Session Types and Behavioural Contracts]</ref> and there is a likely connection between computational power of a process calculus and the strength of the corresponding type theory. | |||
The most simple variant of the calculus | The most simple variant of the calculus is lacking any scoped constructs and is called '''zero-order''' as a reference to [[Wikipedia:Zeroth-order_logic|zeroth-order logic]]. | ||
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 | 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. | ||
== Zero-order calculus == | == Zero-order calculus == | ||