Siguiente: Una formalización de gramáticas
Un nivel arriba: Reglas de transformación
Anterior: KENNINGS: Poesía antigua islandesa
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.
|
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.
|
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.
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