Esta no es una respuesta completa, pero espero que dé una idea de los problemas.
Definiciones y notación
Voy a hablar de expresiones en lugar de pájaros . Un $L$ -expresión es una expresión que sólo contiene $L$ s y paréntesis. El tamaño de un $L$ -expresión es el número de $L$ s que contiene, y se escribe $|\textrm{expr}|$ .
A menos que me haya perdido algo, Smullyan no define lo que quiere decir con $=$ . Esto es más sutil de lo que podría parecer a primera vista. Podemos considerar al menos tres tipos de igualdad de expresiones. Equivalencia estructural ( $=_S$ ) significa que las expresiones son idénticas aparte de los paréntesis opcionales: por ejemplo $L L L =_S (L L) L$ . Equivalencia intensional ( $=_I$ ) significa que las expresiones pueden expandirse utilizando las reglas de los combinadores para obtener expresiones estructuralmente equivalentes. Equivalencia extensional ( $=_E$ ) significa que las expresiones se "comportan" de forma idéntica, en el sentido de que no hay ninguna serie de argumentos que puedas suministrar que haga que den resultados claramente diferentes. Por ejemplo, si has leído algunos capítulos posteriores, $S K K =_E I$ .
A $\beta$ -reducción es la aplicación de la regla de expansión $Lxy = x(yy)$ en algún lugar dentro de una expresión. Utilizaré la notación $A \rightarrow_\beta B$ para significar que $A$ puede reducirse a una expresión estructuralmente equivalente a $B$ por un solo $\beta$ -reducción, y $A \rightarrow_\beta^* B$ para significar que $A$ puede reducirse a una expresión estructuralmente equivalente a $B$ por cero o más $\beta$ -reducciones.
Una expresión es normal si no tiene ninguna posibilidad $\beta$ -reducciones. Nótese que esto no tiene nada que ver con la definición de normal dada para el problema 8 del capítulo 9. Una expresión no normal $A$ es normalizable si hay una expresión normal $B$ tal que $A \rightarrow_\beta^* B$ .
Normal $L$ -Las expresiones son raras
Para ser precisos: hay exactamente una normalidad $L$ -para cualquier tamaño. Podemos definir la normal $L$ -expresión del tamaño $n$ , $N_n$ , de forma recursiva: $$\begin{eqnarray}N_1 & = & L \\ N_{n+1} & = & L (N_n)\end{eqnarray}$$
La forma más fácil para mí de ver por qué esto es correcto es dibujar árboles mostrando el paréntesis, pero MathJax no soporta eso. El punto clave es que $(L x) y$ es $\beta$ -reducible, por lo que cualquier secuencia de tres subexpresiones en un $L$ -La expresión debe ir entre paréntesis como $L(x y)$ .
Normalizable $L$ -Las expresiones son raras
Para ser precisos: no hay ningún $L$ -expresiones de tamaño 1 o 2, y para cada tamaño $n \ge 3$ hay exactamente una expresión no normalizada pero normalizable, $M_n$ que también puede definirse de forma recursiva: $$\begin{eqnarray}M_3 & = & L L L\\ M_{n+1} & = & L (M_n)\end{eqnarray}$$
La prueba es trabajar hacia atrás desde $N_n$ . A $\beta$ -reducción de un $L$ -resulta en una subexpresión de la forma $x(yy)$ y la única subexpresión de $N_n$ de la forma $x(yy)$ es la copia anidada de $N_3$ . Desenrollando eso como $L(L L) \,{}_\beta\leftarrow L L L$ da $M_n$ como se describe. Pero $M_n$ ahora no tiene subexpresiones de la forma $x(yy)$ en absoluto, por lo que no hay expresiones que $\beta$ -reduce a ella.
$L$ -Las expresiones nunca se reducen
Dado que un $L$ -expresión no es normal, cada $\beta$ -La reducción que se le aplique debe dejar el tamaño sin cambios o aumentarlo. La razón es sencilla: $|L x y| = |L| + |x| + |y| = 1 + |x| + |y|$ ; $|x(yy)| = |x| + 2 |y|$ y $|y| \ge 1$ . De hecho, esto demuestra que tenemos la propiedad más fuerte de que si $A \rightarrow_\beta B$ entonces $|B| > |A|$ a menos que $A =_S L x L$ para algunos $x$ .
Ponerlo en común: ¿cuál es el problema?
Limitémonos por ahora a la equivalencia intensional. (La mayoría de los ejemplos, si no todos, hasta este punto del libro han utilizado la equivalencia intensional en lugar de la extensional, así que parece razonable). Tenemos una expresión candidata $E$ y queremos determinar si $E =_I EE$ . A menos que $E = N_{|E|}$ o $E = M_{|E|}$ obtenemos una cadena infinita de $\beta$ -expansiones en expresiones cada vez mayores. (Es cierto que no he descartado la circular $\beta$ -expansión, como ocurre con $M M \rightarrow_\beta M M$ donde $M$ es el ruiseñor, pero te dejo ese hueco para que lo cierres si quieres). De la misma manera, $EE$ da una secuencia infinita de expresiones siempre crecientes. Comprobar si dos secuencias infinitas se cruzan no es, en general, fácil. (Si has leído mucho más en el libro, sabrás que comprobar si dos expresiones son equivalentes es incalculable ).
La mejor posibilidad podría ser examinar de nuevo el significado de la equivalencia intensional. Cuando la definí por primera vez, no había definido $\beta$ -expansión. Ahora podemos decir que $A =_I B \textrm{ iff } \exists C : A \rightarrow_\beta^* C \textrm{ and } B \rightarrow_\beta^* C$ . ¿Y si es posible parametrizar $\rightarrow_\beta^*$ por el número máximo de reducciones realizadas, y luego probar algún tipo de requisitos estructurales en $E$ y $EE$ en función de ese límite?
Ejemplo exploratorio
A modo de ejemplo, supongamos que $E$ es el El más pequeño egocéntrico $L$ -expresión y (esta es una suposición injustificada) que hay un directo equivalencia intensional $E \rightarrow_\beta^* EE$ . (Desde $L$ -las expresiones nunca se reducen, es imposible que $EE \rightarrow_\beta^* E$ ).
$EE =_S (E)(E)$ . Si tuviéramos $E = xy$ con $x \rightarrow_\beta^* E$ y $y \rightarrow_\beta^* E$ entonces $x$ y $y$ serían expresiones más pequeñas que $E$ pero ambos serían egocéntricos, lo que supondría una contradicción con la minimidad de $E$ .
Entonces debe haber en algún momento un nivel superior $\beta$ -reducción: es decir $E \rightarrow_\beta^* L A B \rightarrow_\beta A (B B)$ con $A \rightarrow_\beta^* E$ y $B B \rightarrow_\beta^* E$ . Esto implica que $|B B| \le |E|$ por lo que a partir de la minimidad de $E$ obtenemos wlog que $E = BB$ (y también que $B$ no es egocéntrico). Pero entonces sólo tenemos que considerar $|B| < 6$ y no hay muchos $L$ -expresiones así de pequeñas:
- $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$ (con dos posibilidades inmediatas $\beta$ -expansión)
- $L L (L L) L =_I L (L L (L L)) L =_I \ldots$ (ídem)
- $ L L (L (L L)) =_I L(L (L L)(L (L L))) =_I \ldots$
Podría ser posible argumentar más sobre la estructura antes de seleccionar cuál de estos casos examinar en detalle, pero ahora que reviso los intentos que garabateé en el tren veo que he estado mezclando la equivalencia intensional y extensional de una manera que invalida completamente mi razonamiento.
