Una quine en cálculo lambda puro

Me gustaría un ejemplo de quine en cálculo lambda puro . Me sorprendió bastante no poder encontrar uno buscando en Google. La página quine enumera quines para muchos idiomas "reales", pero no para el cálculo lambda.

Por supuesto, esto significa definir lo que quiero decir con una quine en el cálculo lambda, que hago a continuación. (Estoy pidiendo algo bastante específico).

En algunos lugares, por ejemplo, Larkin y Stocks (2004), veo lo siguiente citado como una expresión "autorreplicante": $(\lambda x.x \; x)\;(\lambda x.x \; x)$ . Esto se reduce a sí mismo después de un solo paso de reducción beta, dándole una sensación de quine de alguna manera. Sin embargo, no se parece a quine porque no termina: las reducciones beta adicionales seguirán produciendo la misma expresión, por lo que nunca se reducirán a la forma normal. Para mí, un quine es un programa que termina y se genera solo, por lo que me gustaría una expresión lambda con esa propiedad.

Por supuesto, cualquier expresión que no contenga redexes ya está en forma normal y, por lo tanto, terminará y se generará. Pero eso es demasiado trivial. Por lo tanto, propongo la siguiente definición con la esperanza de que admitirá una solución no trivial:

definición (provisional): Una quine en cálculo lambda es una expresión de la forma

(λ x . A)

$(\lambda x . A)$ (donde

A

$A$ representa alguna expresión específica de cálculo lambda) tal que

((λ x . A) y)

$((\lambda x . A)\,\, y)$ convierte en

(λ x . A)

$(\lambda x . A)$ , o algo equivalente a él bajo cambios de nombres de variables, cuando se reduce a la forma normal, paracualquierentrada

y

$y$ .

Dado que el cálculo lambda es tan equivalente a Turing como cualquier otro idioma, parece que esto debería ser posible, pero mi cálculo lambda está oxidado, así que no puedo pensar en un ejemplo.

Referencia

James Larkin y Phil Stocks. (2004) "Expresiones autorreplicantes en el cálculo de Lambda" Conferencias en Investigación y práctica en tecnología de la información, 26 (1), 167-173. http://epublications.bond.edu.au/infotech_pubs/158

lambda-calculus Nathaniel
fuente

No es una respuesta a mi pregunta, pero para mi propia referencia futura (y para futuros visitantes) será útil tener un enlace a wiki.haskell.org/Combinatory_logic , en el que alguien tiene pensamientos mucho más profundos sobre quines que yo.

Nathaniel

Tenga en cuenta que una quine necesita producir su propio código fuente . Producir la función que representa no es suficiente.

PyRulez

@PyRulez, ¿cuál es el código fuente de una expresión lambda? Si se trata de una secuencia de caracteres, es imposible que una expresión lambda la muestre y, en consecuencia, podemos definir que la palabra "quine" signifique algo ligeramente diferente para las expresiones lambda sin temor a la ambigüedad. Por otro lado, si piensa que el código fuente es la expresión lambda misma, entonces "el código fuente" y "la función que representa" son lo mismo. Entonces creo que estoy bien aquí.

Nathaniel

Hay una iglesia que codifica las cuerdas. Un cálculo lambda quine debería generar la codificación de la iglesia de la cadena de caracteres que lo representan.

PyRulez

Claro, eso no es difícil de hacer, si lo define de esa manera. Esta pregunta era sobre algo diferente.

Nathaniel

Respuestas:

Desea un término tal que : $Q$ $\forall M \in \Lambda$

Q M ⊳_{β} Q

$QM \rhd_\beta Q$

No especificaré más restricciones sobre (por ejemplo, con respecto a su forma y si se está normalizando) y le mostraré que definitivamente no debe estar normalizándose. $Q$

Suponga que está en forma normal. Elija (podemos hacerlo porque el teorema debe mantenerse para todas las ). Luego hay tres casos. $Q$ $M \equiv x$ $M$
- es un átomo . Entonces . Esto no es reducible a . $Q$ $a$ $QM \equiv ax$ $a$
- es alguna aplicación . Entonces . es una forma normal por hipótesis, por lo que también está en forma normal y no es reducible a . $Q$ $(RS)$ $QM \equiv (RS)x$ $(RS)$ $(RS)x$ $(RS)$
- es alguna abstracción (sise supone que es libre en , entonces, por simplicidad, podemos elegir equivalente a cualquier variable abstracta). Entonces . Como está en forma normal, también lo está $Q$ $(\lambda x.A)$ $x$ $A$ $M$ $\lambda$ $QM \equiv (\lambda x.A)x \rhd_\beta A[x/x] \equiv A$ $(\lambda x.A)$ $A$ . En consecuencia, no podemos reducir a . $A$ $(\lambda x.A)$
Entonces, si tal existe, no puede estar en forma normal. $Q$
Para completar, suponga que tiene una forma normal, pero no está en forma normal (tal vez se está normalizando débilmente), es decir, con tal que : $Q$ $\exists N \in \beta\text{-nf}$ $N \not\equiv Q$ $\forall M \in \Lambda$
$Q M ⊳_{β} Q ⊳_{β} N$

Entonces con también debe existir una secuencia de reducción , porque: $M \equiv x$ $Qx \rhd_\beta Nx \rhd_\beta N$
- es posible por el hecho de que . $Qx \rhd_\beta Nx$ $Q \rhd_\beta N$
- debe normalizarse ya que es un nf es solo un átomo. $Nx$ $N$ $\beta$ $x$
- Si se normalizara a otra cosa que no sea , entonces tiene dos nfs, lo cual no es posible por un corolario del teorema de Church-Rosser. (El teorema de Church-Rosser esencialmente establece que las reducciones son confluentes, como probablemente ya sepa). $Nx$ $N$ $Qx$ $\beta$
Pero tenga en cuenta que no es posible mediante el argumento (1) anterior, por lo que nuestra suposición de que tiene una forma normal no es sostenible. $Nx \rhd_\beta N$ $Q$
Si permitimos tal , entonces, estamos seguros de que debe ser no normalizado. En ese caso, simplemente podemos usar un combinador que elimine cualquier argumento que reciba. La sugerencia de Denis funciona bien: Luego en solo dos reducciones : $Q$
$Q \equiv (λ z . (λ x . λ z . (x x)) (λ x . λ z . (x x)))$ $Q \equiv (\lambda z.(λx.λz.(x x)) (λx.λz.(x x)))$ $\beta$ $\begin{aligned} Q M & \equiv (λ z . (λ x . λ z . (x x)) (λ x . λ z . (x x))) M \\ ⊳_{1 β} (λ x . λ z . (x x)) (λ x . λ z . (x x)) \\ ⊳_{1 β} (λ z . ((λ x . λ z . (x x)) (λ x . λ z . (x x))) \\ \equiv Q \end{aligned}$ $\begin{align} QM &\equiv (\lambda z.(λx.λz.(x x)) (λx.λz.(x x))) M \\ & \rhd_{1\beta} (λx.λz.(x x)) (λx.λz.(x x)) \\ & \rhd_{1\beta} (λz.((λx.λz.(x x))(λx.λz.(x x))) \\ & \equiv Q \end{align}$

Este resultado no es muy sorprendente, ya que esencialmente está pidiendo un término que elimine cualquier argumento que reciba, y esto es algo que a menudo veo mencionado como una aplicación directa del teorema del punto fijo.

Roy O.
fuente

Si pudiera aceptar la respuesta de Denis también, lo haría, pero (después de haber aprendido un poco más y haberlo entendido completamente) fue esta respuesta la que realmente me convenció de que este "combinador de quine" no puede ser implementado por un expresión lambda en forma normal.

Nathaniel

Por un lado, esto es imposible, porque se supone que una quine genera su propio código, y el cálculo lambda puro no tiene medios para realizar la salida.

Por otro lado, si supone que el término resultante es la salida, entonces cada forma normal es una quine.

$(\lambda x. x)$ $(\lambda x. x)$ $(\lambda x. x)$

Dave Clarke
fuente

Ese es un punto interesante. En la pregunta, traté de dar una definición de lo que podría contar como una quina no trivial en el cálculo lambda: una función que, cuando se aplica a cualquier entrada, beta se reduce a sí misma (hasta sustituciones de nombres variables). Puede ser que esto sea imposible, pero no es obvio, al menos para mí.

Nathaniel

Aquí hay una propuesta:

$A$ $f=\lambda t. (\lambda z.t)$

$Y=\lambda g.((\lambda x.g\ (x\ x))\ (\lambda x.g\ (x\ x)))$ $A=Y f=(\lambda x.\lambda z.(x\ x))\ (\lambda x.\lambda z.(x\ x))$

$A$ $A$ $\lambda z.A$ $y$ $(\lambda z.A)y \to_\beta A \to_\beta (\lambda z.A)$

Denis
fuente

Esto es bastante bueno, y responde la pregunta tal como la hice, así que me siento mal por no aceptarlo, pero desafortunadamente cometí un pequeño error al especificar lo que quiero. En realidad quiero

(λ z . A) y

$(\lambda z.A)\;y$ to become

(λ z . A)

$(\lambda z.A)$ when reduced to normal form, not just after a beta reduction step. (See the updated question for why.) This means that

A

$A$ can't contain any redexes, because if it does then the reduction will not terminate.

Nathaniel

Ah in this case i'm pretty sure it is impossible, because of the following intuition (not a proof but almost): you want

y

$y$ to play no role since it has to work for every

y

$y$ , so

y

$y$ should not be free in

A

$A$ . Then

(λ z . A) y

$(\lambda z.A)y$ just reduces to

A

$A$ . Now you want

A

$A$ to reduce to

λ z . A

$\lambda z.A$ . This last expression cannot be a normal form, since the

A

$A$ adentro se puede reducir nuevamente ...

Denis

Este comportamiento no es muy sorprendente, porque diluye la "impresión" de

λ - c a l c u l u s

$\lambda-calculus$ son nuevamente instrucciones, una quine que imprime su propio código siempre es ejecutable. Lo que está pidiendo es similar a pedir una cantidad tal que si ejecuta la salida, no imprime nada (lo cual es imposible por definición).

Denis

Ahh, you're right of course. I should have seen that. I'm not sure whether to accept your answer or edit the question to ask for a better definition. I'll give it a bit of thought. (It still seems to me that it should be possible to give a non-trivial definition where you're asking for something that will terminate, but I'm not sure how.)

Nathaniel

Though having said that, is it really true that

z

$z$ (I assume you mean

z

$z$ ) has to not be free in

A

$A$ ? E.g.

A

$A$ could be something along the lines of if z==p then return q, otherwise return q. (Pseudocode because I'm not sure if it's even possible to define the equality operator for arbitrary expressions in lambda calculus, but I think you see what I mean.)

Nathaniel