Question (29, p. 81). Let me tell you the most surprising thing I know about larks: Suppose we are given that the forest contains a lark $L$ and we are not given any other information. From just this one fact alone, it can be proved that at least on bird in the forest must be egocentric!

The proof of this is a bit tricky. Given the lark $L$, we can actually write down an expression for an egocentric bird--and we can write it using just the letter $L$, with parentheses, of course. The shortest expression that I have been able to find has a length of 12, not counting parentheses. That is, we can write $L$ twelve times and then by parenthesizing it the right way, have the answer. Care to try it? Can you find a shorter expression than mine that works? Can it be proved that there is no shorter expression in $L$ that works? I don't know! At any rate, see if you can find an egocentric bird, given the bird $L$.

Definition (lark, p. 80). A bird $L$ is called a lark if for any birds $x$ and $y$ the following holds: $$(Lx)y = x(yy).$$

Definition (egocentric, p. 75). A bird $x$ is called egocentric (sometimes narcissistic) if it is fond of itself--that is, if $x$'s response to $x$ is $x$. In symbols, $x$ is egocentric if $xx = x$.

On page 88, Smullyan gives the (length 12) solution $((L(LL)) (L(LL))) ((L(LL)) (L(LL)))$. How can I prove that there is or is not a shorter expression for an egocentric bird in $L$?

  • 2
    $\begingroup$ Please, post the question in full, and also describe your attempts at the question so far. $\endgroup$ – Kirill Oct 23 '13 at 1:52
  • 1
    $\begingroup$ You may be able to do this computationally. The $n^\text{th}$ Catalan number $C_n$ is the number of ways to parenthesize an expression with $n+1$ symbols. Iterate over each the parenthesizations of $L$, $LL$, $LLL$, ..., and $L^{11}$ and check if that parenthesization gives an egocentric bird. You'll only have to check $C_1 + C_2 + \ldots + C_{10} = 23713$ cases. $\endgroup$ – Snowball Oct 23 '13 at 20:28
  • 1
    $\begingroup$ @Snowball, the problem there is that checking whether two combinator expressions are equivalent is undecidable in the general case, and the behaviour of $L L (L L) = L (L L (L L)) = \lambda x. L L (L L) (x x)$ seems to rule out testing extensionality for small cases, looking for a counterexample, as a strategy. $\endgroup$ – Peter Taylor Feb 24 '14 at 8:16

This isn't a full answer, but I hope it will give an idea of the problems.

Definitions and notation

I'm going to talk about expressions rather than birds. An $L$-expression is an expression containing only $L$s and brackets. The size of an $L$-expression is the number of $L$s it contains, and is written $|\textrm{expr}|$.

Unless I've missed something, Smullyan doesn't define what he means by $=$. This is more subtle than it might at first appear. We can consider at least three types of equality of expressions. Structural equivalence ($=_S$) means that the expressions are identical apart from optional brackets: e.g. $L L L =_S (L L) L$. Intensional equivalence ($=_I$) means that the expressions can be expanded using the combinator rules to give structurally equivalent expressions. Extensional equivalence ($=_E$) means that the expressions "behave" identically, in the sense that there's no series of arguments you can supply which cause them to give clearly different results. E.g. if you've read some later chapters, $S K K =_E I$.

A $\beta$-reduction is the application of the expansion rule $Lxy = x(yy)$ somewhere within an expression. I will use the notation $A \rightarrow_\beta B$ to mean that $A$ can be reduced to an expression which is structurally equivalent to $B$ by a single $\beta$-reduction, and $A \rightarrow_\beta^* B$ to mean that $A$ can be reduced to an expression which is structurally equivalent to $B$ by zero or more $\beta$-reductions.

An expression is normal if it has no possible $\beta$-reductions. Note that this is not at all related to the definition of normal given for problem 8 of chapter 9. An non-normal expression $A$ is normalisable if there is a normal expression $B$ such that $A \rightarrow_\beta^* B$.

Normal $L$-expressions are rare

To be precise: there is exactly one normal $L$-expression for any given size. We can define the normal $L$-expression of size $n$, $N_n$, recursively: $$\begin{eqnarray}N_1 & = & L \\ N_{n+1} & = & L (N_n)\end{eqnarray}$$

The easiest way for me to see why this is correct is to draw trees showing the parenthesisation, but MathJax doesn't support that. The key point is that $(L x) y$ is $\beta$-reducible, so any sequence of three subexpressions in a normal $L$-expression must be parenthesised as $L(x y)$.

Normalisable $L$-expressions are rare

To be precise: there are no non-normal $L$-expressions of size 1 or 2, and for every size $n \ge 3$ there is exactly one non-normal but normalisable expression, $M_n$, which again can be defined recursively: $$\begin{eqnarray}M_3 & = & L L L\\ M_{n+1} & = & L (M_n)\end{eqnarray}$$

Proof is by working backwards from $N_n$. A $\beta$-reduction of an $L$-expression results in a subexpression of the form $x(yy)$, and the only subexpression of $N_n$ of the form $x(yy)$ is the nested copy of $N_3$. Unrolling that as $L(L L) \,{}_\beta\leftarrow L L L$ gives $M_n$ as described. But $M_n$ now has no subexpressions of the form $x(yy)$ at all, so there are no expressions which $\beta$-reduce to it.

$L$-expressions never get smaller

Given that an $L$-expression is not normal, every $\beta$-reduction applied to it must either leave the size unchanged or increase it. The reason is simple: $|L x y| = |L| + |x| + |y| = 1 + |x| + |y|$; $|x(yy)| = |x| + 2 |y|$; and $|y| \ge 1$. In fact, this shows that we have the stronger property that if $A \rightarrow_\beta B$ then $|B| > |A|$ unless $A =_S L x L$ for some $x$.

Putting it together: what's the problem?

Let's restrict ourselves for the present to intensional equivalence. (Most, if not all, of the examples to this point in the book have used intensional equivalence rather than extensional, so it seems reasonable). We have a candidate expression $E$ and we want to determine whether $E =_I EE$. Unless $E = N_{|E|}$ or $E = M_{|E|}$, we get an infinite chain of $\beta$-expansions into ever-growing expressions. (It's true that I haven't actually ruled out circular $\beta$-expansion, as happens with $M M \rightarrow_\beta M M$ where $M$ is the mockingbird, but I'll leave that gap for you to close if you want). Similarly, $EE$ gives an infinite sequence of ever-growing expressions. Checking to see whether two infinite sequences intersect is not, in general, easy. (If you've read a lot further into the book, you'll know that checking to see whether two expressions are equivalent is uncomputable).

The best possibility might be to look again at the meaning of intensional equivalence. When I first defined it, I hadn't defined $\beta$-expansion. We can now say that $A =_I B \textrm{ iff } \exists C : A \rightarrow_\beta^* C \textrm{ and } B \rightarrow_\beta^* C$. What if it's possible to parameterise $\rightarrow_\beta^*$ by the maximum number of reductions performed, and then to prove some kind of structural requirements on $E$ and $EE$ as a function of that limit?

Exploratory example

By way of example, let's suppose that $E$ is the smallest egocentric $L$-expression and (this is an unjustified assumption) that there is a direct intensional equivalence $E \rightarrow_\beta^* EE$. (Since $L$-expressions never get smaller, it's impossible that $EE \rightarrow_\beta^* E$).

$EE =_S (E)(E)$. If we had $E = xy$ with $x \rightarrow_\beta^* E$ and $y \rightarrow_\beta^* E$ then $x$ and $y$ would be smaller expressions than $E$ but would both be egocentric, giving a contradiction to the minimality of $E$.

Then there must be at some point a top-level $\beta$-reduction: i.e. $E \rightarrow_\beta^* L A B \rightarrow_\beta A (B B)$ with $A \rightarrow_\beta^* E$ and $B B \rightarrow_\beta^* E$. That implies that $|B B| \le |E|$, so from the minimality of $E$ we get wlog that $E = BB$ (and also that $B$ is not egocentric). But then we only need consider $|B| < 6$, and there aren't many $L$-expressions that small:

  • $L =_S N_1$
  • $L L =_S N_2$
  • $M_3 =_S L L L =_I L(L L) =_S N_3$
  • $M_4 =_S L(L L L) =_ I L(L(LL)) =_S N_4$
  • $L (L L) L =_I L L (L L) =_I L (L L (LL)) =_I \ldots$
  • $M_5 =_I N_5$
  • $L(L(LL)) L =_I L(LL)(L L) =_I LL(L L(L L)) =_I \ldots$ (with two immediately possible $\beta$-expansions)
  • $L L (L L) L =_I L (L L (L L)) L =_I \ldots$ (ditto)
  • $ L L (L (L L)) =_I L(L (L L)(L (L L))) =_I \ldots$

It might be possible to argue further about the structure before selecting which of these cases to examine in detail, but now that I review the attempts I scribbled on the train I see that I've been mixing intensional and extensional equivalence in a way which completely invalidates my reasoning.

  • $\begingroup$ NB I've attempted to test all expressions of the form $BB$ where $|B| < 6$ by beta-expanding repeatedly (using a priority queue by size of expression) and checking for each expression $XY$ so reached whether both $X$ and $Y$ had previously been encountered. The program failed with a stack overflow when looking for beta-expansions in a 1001-$L$ expression. $(N_3 N_3)(N_3 N_3)$, on the other hand, succeeds at the first opportunity with a 24-$L$ expression. So certainly there's no smaller solution which behaves as nicely as $(N_3 N_3)(N_3 N_3)$. $\endgroup$ – Peter Taylor Feb 27 '14 at 16:33
  • $\begingroup$ The stack overflow was due to $LL(LL) \rightarrow_{\beta} L(LL(LL))$. Manually eliminating that case, I managed to run the others for tens of thousands of beta-expansions and stopped when the program was using 14GB of memory. They were all expanded to at least 3 times their starting size. $\endgroup$ – Peter Taylor Feb 27 '14 at 17:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.