Siguiente: Virus en programas-while Un nivel arriba: Teoría de la recursividad Anterior: Teoremas de recursión

Teoremas de autorreproducción

Teorema 5.1 (de Autorreproducción)   Existe un programa cuya función es escribir su propio índice, es decir,

$$\exists\;k_0\in N:\;\lfloor k_0\rfloor:k\mapsto \lfloor k_0\rfloor(k) = k_0.$$

En efecto, sea $\pi:(x,y)\mapsto x$. $\pi$ es programable, i.e. $\pi\in\mbox{\rm\rm Programas-{\bf while }}$. Sea $k_0=\lceil \pi\rceil$ su índice. Por el teorema de parametrización, $\exists\,h\in\mbox{\rm\rm Programas-{\bf while }}\forall k,x,y:\quad\lfloor h(k,x)\rfloor(y)=\lfloor k\rfloor(x,y).$ La función $g:x\mapsto h(k_0,x)$ es programable. Por tanto, por el teorema de la recursión podemos encontrar un punto fijo para la enumeración ``módulo'' g. Sea $k_g\in N$ tal que $\lfloor k_g\rfloor\equiv \lfloor g(k_g)\rfloor$. Se tiene entonces, $\forall\,m:$

$$\begin{array}{rcll} \lfloor k_g\rfloor(m) &=&\lfloor g(k_g)\... ..._g &\mbox{\rm : porque $\lfloor k_0\rfloor=\pi$.} \end{array}$$

Observación 5.1   Un sistema autorrepresentable puede contener algunas otras funciones primitivas y contener también programas que se autorreproducen y realizan otras funciones.

En efecto, sea $S=(\mbox{\it Primi},\mbox{\it RComp})$ un sistema de programación y sea $f:N\rightarrow N$ una función cualquiera. Sea $S'=(\mbox{\it Primi}',\mbox{\it RComp}')$ el sistema donde

$$\begin{eqnarray*}\mbox{\it Primi}' &=& \mbox{\it Primi}\cup\{f\} \\ \mbox{\it RComp}' &=& \{(f,\rho)\vert\rho\in\mbox{\it RComp}\}. \end{eqnarray*}$$

Así todo programa en S' consta de un programa en S con la función f adjunta: $g'\in S' \;\Leftrightarrow\; \exists g\in S: g'=(f,g).$ Pues bien, puede verse que vale la siguiente

Proposición 5.1   S' es un sistema autorrepresentable siempre que S lo sea.

Consecuentemente S' posee una función ``autorreproductora'', sólo que en S' el programa que se autorreproduce

• realiza la función primitiva f, y
• crea una ``copia'' de sí mismo

Si k₀ es el índice de un programa autorreproductor en S', el programa $\lfloor k_0 \rfloor$ es propiamente, lo que en la actualidad llamamos, un ``virus''.
Siguiente: Virus en programas-while Un nivel arriba: Teoría de la recursividad Anterior: Teoremas de recursión