Resumen

En este trabajo estudiamos los quines, definidos como programas sin input cuyo output es su propio código. Primero, se presentan los resultados teóricos de Kleene que garantizan la existencia de quines y proveen una forma de construirlos. Luego, se revela la estructura fundamental que obedecen los quines a través de una construcción con máquinas de Turing. Por último, se presentan un quine en C à la Turing y un quine en LIS à la Kleene.

Introducción

En las Upaniṣad se nos dice que el mundo origina de un huevo cósmico dentro del cual Brahma, el creador de todas las cosas, se creó a sí mismo. Escoto Erígena, en su División de la naturaleza, enseña que Dios, al crear, se crea. William Blake, en su extraño libro profético Book of Urizen, expone su cosmogonía y dice de Urizen que es un "bastardo" por ser self-created: no tiene por padre o madre más que a sí mismo. Y el budismo, al menos en su variante mahayana, habla de cinco budas originarios y eternos que son "self-born".

Estas imágenes son antiguas y bellas, pero no es claro si son posibles. No podemos pedir al misticismo o la mitología que respeten la realidad sensible, pero sí que al menos no incurran en contradicciones. Preguntamos entonces: ¿puede algo nacer de sí mismo? ¿Son posibles el Dios de Erígena, el Brahma del hinduismo, el Urizen de Blake o los cinco budas?

En este trabajo, estudiaremos programas que confirman la consistencia lógica de los símbolos citados antes: los quines. Son programas que no toman input e imprimen su propio código. Son entes auto-replicantes, auto-creadores: nacen de su propio vientre como un exótico dios oriental, y encarnan aquel aforismo de Ángelus Silesius: Me he convertido en lo que ya era, y soy lo que ya fui.

Los quines son interesantes porque, a primera vista, parece imposible diseñar un sistema capaz de auto-replicarse. Tal sistema debería poseer, por un lado, la totalidad de su propia información, y por otro la información necesaria para efectuar la replicación. Esto resulta en un bucle infinito: cualquier parte encargada de replicar el sistema también debe ser replicada, lo que exige otro mecanismo para replicar esa parte, que a su vez debe ser replicado, y así ad nauseam...

Auto-referencia y auto-replicación

Los quines caen en la categoría de fenómenos indirectamente auto-referenciales. Una cosa es indirectamente auto-referencial si se denota a sí misma no explícitamente, sino a través de alguna forma adecuada de representación. En lógica, el ejemplo paradigmático son las sentencias que dicen algo acerca de su propio número de Gödel. La auto-referencia indirecta puede evitar los problemas usuales de la auto-referencia directa—e.g. la recursión infinita o la inducción de paradojas—. En este sentido, los quines pertenecen a un tipo de fenómeno bien estudiado: nihil novum sub sole.

Por el contrario, el interés por diseñar sistemas con la capacidad de auto-replicarse es relativamente nuevo. El mundo natural, incluso obviando la división celular y la mitosis, evidencia que tales sistemas son posibles—considérese, v.g., la reproducción asexuada—. A su vez, el mecanicismo permitió a figuras como Leibniz y Descartes entretener la tesis de que los seres vivos no eran, en última instancia, más que máquinas. Pero aunque esta tesis implica la factibilidad de diseñar máquinas auto-replicadoras, el problema de la auto-reproducción no fue considerado por ninguna figura del racionalismo o posterior.

Habría que esperar al siglo XX, con el descubrimiento del ADN y el desarrollo paralelo de la computación, para que el diseño de sistemas auto-replicadores fuera considerado seriamente. Los lógicos que más desarrollaron este interés fueron von Neumann, con su universal constructor, y Kleene con su teorema de la recursión.

Kleene

Sea $\mathcal{F}$ el conjunto de funciones parciales computables. La aritmetización de la sintaxis dada por Gödel establece una relación biyectiva entre el conjunto de programas (en el sentido de máquinas de Turing u otro modelo equivalente) y los números naturales. Por lo tanto, como $\mathcal{F}$ es recursivamente enumerable, podemos dar la enumeración:

$$ \varphi_1, \varphi_2, \ldots $$

tal que $\varphi_k$ es la función computada por el programa $k$. Denotamos con $\varphi$ la función universal, i.e. la función tal que $\varphi(p, x) = \varphi_p(x)$, cuya existencia es garantizada por el teorema UTM [5].

El teorema $S_n^m$

Un resultado significativo dado por Kleene es que la currificación de una función computable es computable. Usualmente, este resultado es conocido como el teorema $S_n^m$ o como teorema del parámetro. Lo más usual es dar el caso de dos variables, donde si $\varphi_p(u, x)$ es la función de dos variables computada por el programa $p$, existe una función computable $S(k, p)$ tal que $\varphi_{S(k, p)}(x) = \varphi_p(k, x)$. Nosotros presentamos la forma general del resultado.

Teorema $S_n^m$

Sea $\mathcal{P}$ un programa arbitrario. Existe una función primitiva recursiva, total y uno a uno
$S_n^m : \mathbb{N}^m \times \mathbb{N}$

$$ \varphi_\mathcal{P}(x_1, \ldots, x_n, y_1, \ldots, y_m) \simeq \varphi_{S_n^m(y_1,\ldots, y_m, \mathcal{P})}(x_1, \ldots, x_n) $$

Este teorema no habla de la computabilidad de la función currificada, sino del proceso de currificación. Es decir, garantiza la existencia de una función "currificadora".

Una interpretación útil es que este teorema es la contraparte del teorema que garantiza la existencia de un programa universal que computa $\varphi$. Así como existe $\varphi$ tal que $\varphi(u) = \varphi_u$, existe $\varphi_{S(k, p)}(x) = \varphi_{p}(k, x)$. Intuitivamente, el programa asociado a $\varphi$ es un intérprete capaz de ejecutar cualquier código fuente dejando todo el input variable, mientras que $S(k, p)$ ejecuta el código fuente de $p$ fijando uno de sus inputs en $k$.

Teorema de la recursión

El teorema de la recursión es un resultado fascinante con muchas aplicaciones. Garantiza que, para toda $f \in \mathcal{F}$, existe un programa $e$ tal que $e$ y $f(e)$ computan la misma función, es decir,
$$ \varphi_e(x) \simeq \varphi_{f(e)}(x) $$

Teorema de la recursión. Sea $f \in \mathcal{F}$ una función total. Entonces existe $e$ tal que $\varphi_e(x) \simeq \varphi_{f(e)}(x)$ .

Prueba:

Definamos $d(u)$ como la función tal que:

$$ \varphi_{d(u)}(z) = \begin{cases} \varphi_{\varphi_u(u)}(z) & \text{si } \varphi_u(u) \text{ converge} \\ \bot & \text{c.c.} \end{cases} $$

Entonces $d(u)$ fija $\varphi_u(u)$ como el primer argumento de la función universal $\varphi(x, z)$. El teorema $S_n^m$ garantiza que dicha función es computable, total y uno a uno.

Como $f$ y $d$ son computables, $f \circ d$ es computable. Por tanto, existe $n$ tal que:

$$ \varphi_n = f \circ d $$

Definimos $e = d(n)$. Como $f$ es total, $\varphi_n(n)$ converge, y entonces:

$$ \varphi_e = \varphi_{d(n)} = \varphi_{\varphi_n(n)} = \varphi_{f(d(n))} = \varphi_{f(e)} \quad \blacksquare $$

Existen extensiones del teorema al caso en que $f$ no es total.

La máquina de Turing $Q$

La construcción dada por Kleene tiene dos problemas: $(a)$ no utiliza ningún modelo de computación (i.e. es estrictamente matemática) y $(b)$ es un tanto arcana. Por lo tanto, antes de utilizarla para dar un quine, será provechoso dar un quine en un modelo universal de computación que nos permita desarrollar una comprensión más sólida del problema. Para este propósito, utilizaremos máquinas de Turing, lo cual revelará la estructura fundamental respetada por los quines: la división entre código e información.

Usemos $\left< T \right>$ para denotar la descripción de una máquina de Turing $T$. Notemos que existe una máquina de Turing que, comenzando con la palabra $w$ en la cinta, escribe la descripción de la máquina de Turing que devuelve constantemente $w$. Usemos $B$ para denotar la máquina que efectúa esta operación y escribe su resultado al comienzo de la cinta. Sea $A$ la máquina que imprime constantemente $\left<B \right>$. Definimos una máquina de Turing $Q$ a partir de $A$ y $B$ como sigue:

• Al iniciar $Q$, $A$ toma el control.
• Al terminar $A$, $B$ toma el control.

Claramente, $\left<Q \right> = \left<A \right> \diamond \left<B \right>$, con $\diamond$ la concatenación de palabras.

¿Cómo se ve la computación efectuada por $Q$? Al iniciar la máquina, $A$ toma el control y escribe $\left<B \right>$, que es la descripción de $B$. Luego $B$ toma el control y, viendo en la cinta $\left<B \right>$, deduce la descripción de la máquina que imprime constantemente $\left<B \right>$ y la imprime al principio de la cinta. Pero dicha máquina es $A$. Es decir que cuando $Q$ termina, en la cinta queda escrito

$$\left<A \right>\diamond\left<B \right> = \left<Q \right>$$

Por lo tanto, $Q$ es un "quine"

Código e información: un quine en C

La máquina de Turing $Q$, con su partición en $A$ y $B$, revela la estructura fundamental de los quines reales: la división entre code y data[4], que nosotros llamaremos código e información. La información es una representación textual del código, y se deriva del código a través de un procedimiento algorítmico. El código usa la información para imprimirse a sí mismo, y luego usa la información para imprimir la información. Esto es posible sólo porque la información es una representación computable, es decir que puede efectuarse algorítmicamente.

En esta sección, daremos un quine en C utilizando la estructura de código/información. Daremos un código que, dependiendo de una byte-array informacion, $(a)$ la imprime crudamente y luego $(b)$ imprime los caracteres ASCII correspondientes a cada byte.

El código, llamado quine.c, es:

#include <stdio.h>

int main (void)
{
  unsigned int i;

  printf ("const unsigned char informacion[] = {");
  for ( i=0 ; i < sizeof(informacion) ; i++ )
    {
      if ( i%8 == 0 )
	    printf ("\n/* %0#6x */",i);
      printf ("  %0#4x,", informacion[i]);
    }
  printf ("\n};\n\n");
  for ( i=0 ; i<sizeof(informacion) ; i++ )
    putchar (informacion[i]);
  return 0;
}

Teniendo el código, la pregunta ahora es: ¿cómo generar la informacion? Para ello, generamos una byte-array que represente el código arriba utilizando el comando:

> xxd -i quine.c quine_data.c

Dicho comando escribe en quine_data.c la siguiente representación de nuestro programa quine.c:

unsigned char quine_c[] = {
  0x0a, 0x23, 0x69, 0x6e, 0x63, 0x6c, 0x75, 0x64, 0x65, 0x20, 0x3c, 0x73,
  0x74, 0x64, 0x69, 0x6f, 0x2e, 0x68, 0x3e, 0x0a, 0x0a, 0x63, 0x6f, 0x6e,
  0x73, 0x74, 0x20, 0x75, 0x6e, 0x73, 0x69, 0x67, 0x6e, 0x65, 0x64, 0x20,
  // Son demasiadas líneas, salteamos con un comentario...
  0x6d, 0x61, 0x63, 0x69, 0x6f, 0x6e, 0x5b, 0x69, 0x5d, 0x29, 0x3b, 0x0a,
  0x20, 0x20, 0x72, 0x65, 0x74, 0x75, 0x72, 0x6e, 0x20, 0x30, 0x3b, 0x0a,
  0x7d, 0x0a
};

Ahora ponemos, en el programa original, la información tal como la generamos:

const unsigned char informacion[] = {
  0x0a, 0x23, 0x69, 0x6e, 0x63, 0x6c, 0x75, 0x64, 0x65, 0x20, 0x3c, 0x73,
  0x74, 0x64, 0x69, 0x6f, 0x2e, 0x68, 0x3e, 0x0a, 0x0a, 0x63, 0x6f, 0x6e,
  0x73, 0x74, 0x20, 0x75, 0x6e, 0x73, 0x69, 0x67, 0x6e, 0x65, 0x64, 0x20,
  // Son demasiadas líneas, salteamos con un comentario...
  0x6d, 0x61, 0x63, 0x69, 0x6f, 0x6e, 0x5b, 0x69, 0x5d, 0x29, 0x3b, 0x0a,
  0x20, 0x20, 0x72, 0x65, 0x74, 0x75, 0x72, 0x6e, 0x20, 0x30, 0x3b, 0x0a,
  0x7d, 0x0a
};

#include <stdio.h>

int main (void)
{
  unsigned int i;

  printf ("const unsigned char informacion[] = {");
  for ( i=0 ; i < sizeof(informacion) ; i++ )
    {
      if ( i%8 == 0 )
	    printf ("\n/* %0#6x */",i);
      printf ("  %0#4x,", informacion[i]);
    }
  printf ("\n};\n\n");
  for ( i=0 ; i<sizeof(informacion) ; i++ )
    putchar (informacion[i]);
  return 0;
}

¿Qué hace este programa? Primero, imprime

const unsigned char informacion [] = {

con lo cual escribe su primera línea. Después itera sobre la byte-array y la imprime cruda, y completa imprimiendo el corchete que la cierra con el punto y coma. Finalmente, con putchar hace un pretty-printing del contenido de la array, que no es más que el código en C desde #include en adelante. Voilá!

Un quine en un lenguaje operativo simple (LIS)

Denoto con LIS al lenguaje de programación imperativo dado por Reynolds en su obra Theories of programming languages. Es un lenguaje extremadamente simple, pero conocemos su semántica denotacional, y por lo tanto si escribimos un quine en él podemos probar formalmente que su output será su propio código. Este formalismo es más interesante, a mi juicio, que el código de un quine en un lenguaje concreto.

Dado un estado $\sigma \in \Sigma$, usamos $[[c]]\sigma$ para denotar la semántica del comando $c \in \text{<comm>}$ en el estado $\sigma$, donde la semántica es una función en $\text{<comm>} \to \Sigma \to \Sigma$.

Extensión de LIS con strings

Sea $\mathcal{P}$ el lenguaje generado por la gramática de LIS. Definimos $\mathcal{L}$ un alfabeto tal que $\mathcal{L}^* \supseteq \mathcal{P}$ y tal que $\textbf{code} \in \mathcal{L}^*$. Entendemos que $\mathcal{L}$ es numerable y damos una numeración arbitraria $\ell_1, \ell_2, \ldots$ Extenderemos el dominio semántico de manera tal que

$$ \Omega \underset{\psi}{\overset{\phi}{\rightleftarrows}} \left( \hat{\Sigma} + \mathbb{Z} \times \Omega + \mathcal{L}^* \times \Omega + \mathbb{Z} \to \Omega \right)_{\perp} $$

La gramática extendida es idéntica a la de LIS con las siguientes novedades:

$$ \begin{array}{rcl} c &::=& \ell_1 \quad \text{Primer caracter de } \mathcal{L} \\ &|& \ell_2 \quad \text{Segundo caracter de } \mathcal{L} \\ &|& \ldots \\ \\ s &::=& c \quad \text{Caracter (char)} \\ &|& \varepsilon \quad \text{String vacía} \\ &|& s\ c \quad \text{String concatenada a caracter} \\ \\ \text{alfvar} &::=& \sim \quad \text{Conjunto numerable de variables alfabéticas} \\ \\ \text{comm} &::=& \mathbf{code}(s) \quad \text{Operación sobre una string } s \\ \end{array} $$

Las semánticas de <string> y <char> no nos importan, aunque lo natural es mapearlos a una tupla correspondiente en $\mathcal{L}^* \times \Omega$. La semántica de $\textbf{code}$ requiere una definición previa.

Definición
Sea $\sigma \in \Sigma$ y $w_1, w_2, \ldots$ una numeración de las variables alfabéticas del lenguaje. Definimos $\delta_\sigma$ como la sustitución que reemplaza $w_1, w_2, \ldots$ por $\sigma ~ w_1, \sigma ~ w_2, \ldots$ respectivamente, excepto para las ocurrencias de $w_i$ que estén a la izquierda de una asignación ($i = 1, 2, \ldots$).

Ahora estamos preparados para definir las semánticas que nos interesan:

Definición
Sea $\sigma \in \Sigma$. Sean $s, w$ meta-variables para una string y una variable alfabética, respectivamente. Entonces:

• $[[ w := s ]] \sigma := [\sigma \mid w : s]$
• $[[ \textbf{code}(s) ]]\sigma := \big< s / \delta_\sigma, ~ \sigma \big>$

Ejemplo
Si $\sigma ~u = \textbf{skip}$, entonces

$$ [[ \textbf{code} (w := u; u; u := \textbf{fail}) ]]\sigma = \left<w := \textbf{skip}; \textbf{skip}; u := \textbf{fail}, \sigma \right> $$

La magia

Sea $u$ una variable alfabética cualquiera. Definimos:

$$ \mathcal{C} := \textbf{code}\big(u := u; u\big) $$

No es difícil ver que, para todo $\gamma \in \Sigma$, con $\gamma u := p$,

$$ [[ \mathcal{C} ]] \gamma = [[ \textbf{code}(u := u; u) ]] \gamma = \left< u := p; p, \gamma \right> $$

Considere el caso en que $p \in \mathcal{P}$ y $FV(p) = {u}$; es decir, el caso en que $\gamma u$ es un programa que depende únicamente de $u$. Entonces la ecuación (1) garantiza que $[[ \mathcal{C} ]]\gamma$ imprime el código que asigna el valor $p$ a $u$ y luego ejecuta $p$.

Esto corresponde exactamente a la función $f \circ d$ en la construcción de Kleene, con \textbf{code} haciendo el papel de $f$. Y si $\mathcal{C}$ corresponde a $f \circ d$, el programa correspondiente a $d(f \circ d)$ es:

$$ e := \big(u := \mathcal{C}; \mathcal{C}\big) $$

donde $\mathcal{C}$ es meta-variable. El teorema de la recursión garantiza que $e$ es un quine. Y en efecto, para todo $\sigma \in \Sigma$:

$$ \begin{align*} [[ e ]] \sigma &= [[ u := \mathcal{C}; \mathcal{C} ]] \sigma \\ &= [[ \mathcal{C} ]][\sigma \mid u : \mathcal{C}] \\ &= [[ \textbf{code}(u := u; u) ]][\sigma \mid u : \mathcal{C}] \\ &= \left< u := \mathcal{C}; \mathcal{C}, [\sigma \mid u : \mathcal{C}] \right> \\ &= \left< e, [\sigma \mid u : \mathcal{C}] \right> \end{align*} $$

Por ende, el output de $e$ en todo estado es su propio código:

$$ \therefore \forall \sigma \in \Sigma: \pi_1^2 \left( [[ e ]]\sigma \right) = e $$

donde $\pi_k^n$ denota la proyección del $k$-ésimo elemento de una $n$-upla.

$\therefore$ $~ e$ es un quine en nuestra extensión de LIS.