Pipe-calculus: Difference between revisions

Pipe-calculus (view source)

460 bytes removed , 22 May 2023

283

edits

@@ Line 61: / Line 61: @@
 === 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 basic variant of the calculus lacks any scoped constructs and is called '''zero-order''' as a reference to [[Wikipedia:Zeroth-order_logic|zeroth-order logic]].
-The most basic 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.
 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.