XGitUrl: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=week2.mdwn;h=49a7e8d5af7632592a80b80b6351058bb97c1a7c;hp=eedc6de0458e1046e2b9ec5bdee7f4ac6dfd28da;hb=193823d816ee0b6ed88532df8ab2d9f43f66daca;hpb=82558787dab095c164d4a6d2cdfceebc9b335698
diff git a/week2.mdwn b/week2.mdwn
index eedc6de0..49a7e8d5 100644
 a/week2.mdwn
+++ b/week2.mdwn
@@ 101,9 +101,8 @@ One can do that with a very spare set of basic combinators. These days the stand
There are some wellknown linguistic applications of Combinatory
Logic, due to Anna Szabolcsi, Mark Steedman, and Pauline Jacobson.
Szabolcsi supposed that the meanings of certain expressions could be
insightfully expressed in the form of combinators.

+They claim that natural language semantics is a combinatory system: that every
+natural language denotation is a combinator.
For instance, Szabolcsi argues that reflexive pronouns are argument
duplicators.
@@ 111,7 +110,7 @@ duplicators.
![reflexive](http://lambda.jimpryor.net/szabolcsireflexive.jpg)
Notice that the semantic value of *himself* is exactly `W`.
The reflexive pronoun in direct object position combines first with the transitive verb (through compositional magic we won't go into here). The result is an intransitive verb phrase that takes a subject argument, duplicates that argument, and feeds the two copies to the transitive verb meaning.
+The reflexive pronoun in direct object position combines with the transitive verb. The result is an intransitive verb phrase that takes a subject argument, duplicates that argument, and feeds the two copies to the transitive verb meaning.
Note that `W <~~> S(CI)`:
@@ 183,6 +182,9 @@ The fifth rule deals with an abstract whose body is an application: the S combin
[Fussy notes: if the original lambda term has free variables in it, so will the combinatory logic translation. Feel free to worry about this, though you should be confident that it makes sense. You should also convince yourself that if the original lambda term contains no free variablesi.e., is a combinatorthen the translation will consist only of S, K, and I (plus parentheses). One other detail: this translation algorithm builds expressions that combine lambdas with combinators. For instance, the translation of our boolean false `\x.\y.y` is `[\x[\y.y]] = [\x.I] = KI`. In the intermediate stage, we have `\x.I`, which mixes combinators in the body of a lambda abstract. It's possible to avoid this if you want to, but it takes some careful thought. See, e.g., Barendregt 1984, page 156.]
+[Various, slightly differing translation schemes from combinatorial logic to the lambda calculus are also possible. These generate different metatheoretical correspondences between the two calculii. Consult Hindley and Seldin for details. Also, note that the combinatorial proof theory needs to be strengthened with axioms beyond anything we've here described in order to make [M] convertible with [N] whenever the original lambdaterms M and N are convertible.]
+
+
Let's check that the translation of the false boolean behaves as expected by feeding it two arbitrary arguments:
KIXY ~~> IY ~~> Y
@@ 324,16 +326,18 @@ The logical system you get when etareduction is added to the proof system has t
> if `M`, `N` are normal forms with no free variables, then M ≡ N
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 L_{1}, ..., L_{n}
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 L_{1}, ..., L_{n}
such that:
M L_{1} ... L_{n} x y ~~> x
N L_{1} ... L_{n} x y ~~> y
That is, closed normal forms that are not just betareduced but also fully etareduced, will be syntactically different iff they yield different values for some arguments. That is, iff their extensions differ.
+So closed betaplusetanormal forms will be syntactically different iff they yield different values for some arguments. That is, iff their extensions differ.
So the proof theory with etareduction added is called "extensional," because its notion of normal form makes syntactic identity of closed normal forms coincide with extensional equivalence.
+See Hindley and Seldin, Chapters 78 and 14, for discussion of what should count as capturing the "extensionality" of these systems, and some outstanding issues.
+
The evaluation strategy which answers Q1 by saying "reduce arguments first" is known as **callbyvalue**. The evaluation strategy which answers Q1 by saying "substitute arguments in unreduced" is known as **callbyname** or **callbyneed** (the difference between these has to do with efficiency, not semantics).
@@ 432,6 +436,7 @@ But is there any method for doing this in generalfor telling, of any given co
* [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 firstorder 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 righthand side is not decidable, questions of provability in firstorder predicate logic must not be decidable either. This was the first proof of the undecidability of firstorder predicate logic.
##[[Lists and Numbers]]##