Content deleted Content added
m Oops, one more missed… |
Basic examples |
||
Line 50:
These remarks imply that for all term <math>t(x_0, \dots, x_n)</math>, the value <math>a := \langle x_0 \rangle \dots \langle x_n \rangle t \downarrow</math> is well-defined and satisfies the two requirements of combinatory completeness.
==Examples==
===First Kleene algebra===
The first Kleene algebra <math>\mathcal{K}_1</math> consists of the set <math>\mathbb{N}</math> with application <math>a b := \phi_a(b)</math>, where <math>\phi_a</math> denotes the <math>a</math>-th partial recursive function in a standard Gödel numbering.
This pca can also be [[relativization|relativized]] to an oracle <math>D \subseteq \mathbb{N}</math>: we define a pca <math>\mathcal{K}_1^D</math> with carrier <math>\mathbb{N}</math> by setting <math>a b := \phi^D_a(b)</math>, where <math>\phi^D_a</math> is the <math>a</math>-th partial recursive function with oracle <math>D</math>.
===Untyped λ-calculus===
We can form a pca (in fact a tca) by quotienting the set of closed (untyped) λ-terms by [[β-equivalence]] and taking the application to be the one inherited from λ-calculus.
==Notes==
| |||