283
edits
Pipe-calculus: Difference between revisions
→Variants and computational power
KalmanKeri (talk | contribs) |
KalmanKeri (talk | contribs) |
||
| Line 63: | Line 63: | ||
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]]. | 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 zeroth-order calculus has a limited computational power. | 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 | In the '''higher-order''' calculus there are lexically scoped variables that can bind arbitrary terms. Intermediate variants can be created by extending the basic calculus with new constructs. Determining the computational power of specific variants of the calculus is of interest. | ||
It is an observation and also a | It is an observation and also a design goal that specific variants of the calculus can recognize specific classes of formal languages in the [[Wikipedia:Chomsky_hierarchy|Chomsky hierarchy]]. For example it is assumed that the zeroth-order calculus with top level recursion can encode [[Wikipedia:Finite-state_machine|finite-state machines]] and as a consequence it can recognize regular languages. | ||
== Informal description == | == Informal description == | ||