next up previous contents
Siguiente: Una formalización de gramáticas Un nivel arriba: Reglas de transformación Anterior: KENNINGS: Poesía antigua islandesa

Algoritmos de Markov

Estos sistemas formalizan procedimientos de cálculo.


Multiplicación por 3 en representación binaria En la tabla (2) presentamos a las producciones, es decir, a las sustituciones que constituyen este sistema de transformaciones.
  
Table 2: Algoritmo de Markov para triplicar números binarios.
\begin{table}\begin{displaymath}\begin{array}{\vert\vert ccc\vert ccc\vert\vert}... ...box{\rm blanco}$\space y $x \in \{ 0 , 1 , b \}$ . \end{center} \end{table}

Como ejemplos de cálculo presentamos en la tabla (3) dos multiplicaciones. En cada una, la derivación en un renglón proviene de la anterior mediante la aplicación de la regla correspondiente al símbolo de estado y las dos literales que lo flanquean.
  
Table 3: Dos ejemplos de la triplicación de números binarios.
\begin{table}\begin{center} a) $\begin{array}[t]{r} 19 \times 3 = 57 \\ 100... ...\ G1001 \\ Hb0001 \\ 100001 \end{array}$ \end{center} \end{table}

Los algoritmos de Markov son equivalentes a otros sistemas de transformación como son las gramáticas formales irrestrictas, las funciones recursivas y las máquinas de Turing. Posteriormente presentaremos con todo detalle estos sistemas. Para concluir esta sección enunciamos la

Tesis 2.1 (de Church)   Cualquier procedimiento efectivamente computable corresponde a un conjunto de transformaciones sintácticas sobre un alfabeto.

Así pues, puesto de manera muy simplificada, se tiene que el concepto de computabilidad efectiva ha de coincidir con el de transformación sintáctica.
next up previous contents
Siguiente: Una formalización de gramáticas Un nivel arriba: Reglas de transformación Anterior: KENNINGS: Poesía antigua islandesa
Guillermo Morales-Luna
2000-06-27