Syntactic equality, reduction, convertibility
=============================================
-Define T to be `(\x. x y) z`. Then T and `(\x. x y) z` are syntactically equal, and we're counting them as syntactically equal to `(\z. z y) z` as well, which we will write as:
+Define N to be `(\x. x y) z`. Then N and `(\x. x y) z` are syntactically equal, and we're counting them as syntactically equal to `(\z. z y) z` as well, which we will write as:
-<pre><code>T ≡ (\x. x y) z ≡ (\z. z y) z
+<pre><code>N ≡ (\x. x y) z ≡ (\z. z y) z
</code></pre>
This:
- T ~~> z y
+ N ~~> z y
-means that T beta-reduces to `z y`. This:
+means that N beta-reduces to `z y`. This:
- M <~~> T
+ M <~~> N
-means that M and T are beta-convertible, that is, that there's something they both reduce to in zero or more steps.
+means that M and N are beta-convertible, that is, that there's something they both reduce to in zero or more steps.
Combinators and Combinatorial Logic
===================================
That is, K throws away its second argument. The reduction rule for S can be constructed by examining
the defining lambda term:
- S = \fgx.fx(gx)
+<pre><code>S ≡ \fgx.fx(gx)</code></pre>
S takes three arguments, duplicates the third argument, and feeds one copy to the first argument and the second copy to the second argument. So:
Throws away the first argument, returns the second argument---yep, it works.
-Here's a more elaborate example of the translation. The goal is to establish that combinators can reverse order, so we use the T combinator, where `T = \x\y.yx`:
+Here's a more elaborate example of the translation. The goal is to establish that combinators can reverse order, so we use the **T** combinator, where <code>T ≡ \x\y.yx</code>:
[\x\y.yx] = [\x[\y.yx]] = [\x.S[\y.y][\y.x]] = [\x.(SI)(Kx)] = S[\x.SI][\x.Kx] = S(K(SI))(S[\x.K][\x.x]) = S(K(SI))(S(KK)I)
We can test this translation by seeing if it behaves like the original lambda term does.
The orginal lambda term lifts its first argument (think of it as reversing the order of its two arguments):
- S(K(SI))(S(KK)I) X Y =
- (K(SI))X ((S(KK)I) X) Y =
- SI ((KK)X (IX)) Y =
- SI (KX) Y =
- IY (KX)Y =
- Y X
+ S(K(SI))(S(KK)I) X Y ~~>
+ (K(SI))X ((S(KK)I) X) Y ~~>
+ SI ((KK)X (IX)) Y ~~>
+ SI (KX) Y ~~>
+ IY (KXY) ~~>
+ Y X
Voilà: the combinator takes any X and Y as arguments, and returns Y applied to X.
A final linguistic application: Steedman's Combinatory Categorial Grammar, where the "Combinatory" is
from combinatory logic (see especially his 2000 book, <cite>The Syntactic Processs</cite>). Steedman attempts to build
-a syntax/semantics interface using a small number of combinators, including T = `\xy.yx`, B = `\fxy.f(xy)`,
+a syntax/semantics interface using a small number of combinators, including T ≡ `\xy.yx`, B ≡ `\fxy.f(xy)`,
and our friend S. Steedman used Smullyan's fanciful bird
names for the combinators, Thrush, Bluebird, and Starling.
\x. M
+When we add eta-reduction to our proof system, we end up reconstruing the meaning of `~~>` and `<~~>` and "normal form", all in terms that permit eta-reduction as well. Sometimes these expressions will be annotated to indicate whether only beta-reduction is allowed (<code>~~><sub>β</sub></code>) or whether both beta- and eta-reduction is allowed (<code>~~><sub>βη</sub></code>).
+
The logical system you get when eta-reduction is added to the proof system has the following property:
> if `M`, `N` are normal forms with no free variables, then <code>M ≡ N</code> iff `M` and `N` behave the same with respect to every possible sequence of arguments.
-That is, when `M` and `N` are (closed normal forms that are) syntactically distinct, there will always be some sequences of arguments <code>L<sub>1</sub>, ..., L<sub>n</sub></code> such that:
+This implies that, when `M` and `N` are (closed normal forms that are) syntactically distinct, there will always be some sequences of arguments <code>L<sub>1</sub>, ..., L<sub>n</sub></code> such that:
<pre><code>M L<sub>1</sub> ... L<sub>n</sub> x y ~~> x
N L<sub>1</sub> ... L<sub>n</sub> x y ~~> y
</code></pre>
-That is, closed normal forms that are not just beta-reduced but also fully eta-reduced, will be syntactically different iff they yield different values for some arguments. That is, iff their extensions differ.
+So closed beta-plus-eta-normal forms will be syntactically different iff they yield different values for some arguments. That is, iff their extensions differ.
So the proof theory with eta-reduction added is called "extensional," because its notion of normal form makes syntactic identity of closed normal forms coincide with extensional equivalence.
* [Scooping the Loop Snooper](http://www.cl.cam.ac.uk/teaching/0910/CompTheory/scooping.pdf), a proof of the undecidability of the halting problem in the style of Dr Seuss by Geoffrey K. Pullum
+Interestingly, Church also set up an association between the lambda calculus and first-order predicate logic, such that, for arbitrary lambda formulas `M` and `N`, some formula would be provable in predicate logic iff `M` and `N` were convertible. So since the right-hand side is not decidable, questions of provability in first-order predicate logic must not be decidable either. This was the first proof of the undecidability of first-order predicate logic.
##[[Lists and Numbers]]##