Siguiente: Teoremas de recursión Un nivel arriba: Virus en programas-while Anterior: Definiciones básicas

Matrices infinitas

Para mostrar que existen virus en el lenguaje de los programas-while necesitaremos arreglos planares infinitos, es decir, matrices cuyos renglones y columnas están siendo indicadas por los números naturales. Una matriz infinita es un arreglo $M=\left[m_{ij}\right]_{i,j\geq 0}$. Denotemos a las matrices infinitas con entradas naturales y con entradas funciones recursivas, respectivamente, como

$$\begin{eqnarray*}I\!\!N^{I\!\!N\times I\!\!N}&=&\{M\vert M\mbox{\rm es matriz in... ...M\vert M\mbox{\rm tiene funciones recursivas como entradas}\}. \end{eqnarray*}$$

Sea $f:I\!\!N\rightarrow I\!\!N$ una función y M una matriz. M se dice ser

cerrada por renglones bajo la función f

si $\forall i_1\exists i_2\forall j:\ \left(f(m_{i_1j})=m_{i_2j}\right),$ es decir, si para cada renglón en M, su imagen bajo la función f aparece también como otro renglón de la matriz M, y

diagonalmente completa

si su diagonal aparece también como un renglón, es decir $\exists i_d\forall j:\ \left(m_{i_dj}=m_{jj}\right).$

Lema 6.1 (Diagonal de punto fijo)   Si f es una función tal que existe una matriz diagonalmente completa cerrada por renglones bajo f entonces f posee un punto fijo, es decir, existe x tal que f(x)=x.

Demostración: Sea M una matriz diagonalmente completa cerrada por renglones bajo f. Sea i_d tal que $\forall j: m_{i_dj}=m_{jj}$. Existe i_e tal que $\forall j: f(m_{i_dj})=m_{i_ej}$. Para j=i_e se tiene f(m_idie)=m=m_idie. Así pues m_idie es un punto fijo de f.
Siguiente: Teoremas de recursión Un nivel arriba: Virus en programas-while Anterior: Definiciones básicas