El denominado algoritmo de Markov fue publicado dentro de “The Theory of Algorithms”, en 1.951, por Andréi Andréyevich Márkov, hijo del matemático ruso del mismo nombre conocido por sus modelos (Cadenas, MDP, etc.).
Lo incluyo debido a que algunas veces el algoritmo se confunde, y cuesta interpretar dónde encajarlo, con respecto de algunos de los algoritmos (Avance-Retroceso, Viterbi, etc.) que se utilizan en los modelos de su padre.
El Algoritmo es una variante de un sistema de reescritura (transformación) de 
frases, es decir: Un sistema con un conjunto de reglas en el cual las palabras o expresiones del lenguaje natural/formal se pueden transformar y reducir a un alfabeto y una gramática propias. Por otro lado, es computacionalmente universal, es decir, adecuado como modelo general de cálculo que puede representar cualquier expresión matemática a partir de su notación simple (puede simular una Máquina de Turing).
En la programación práctica (no teórica), hace que las tareas más triviales sean muy tediosas, originando un programa galimatías. Sí os causa interés podéis acercaros al lenguaje Panon-X (Programmazione Algoritmi Non Numerici), AXLE (Axiomatic System for String Transformation) y otros denominados GMA (Generalized Markov Algorithms). A continuación el inico de un programa escrito en Panon-1B.
^= CM * THE SYMBOL ^ = LET * DENOTES THE CLASS OF LETTERS
THE SYMBOL ^ = DCM * DENOTES THE CLASS OF DUMMY CHARACTERS
*= CD * ^E ^= / * ^=LET
^= / * (^E ^OP ^E *)
^= CD * ^OP ^= / * +^=/ * - =/ * *=/ * /
^= TR */0 ^ == * # ^= GOTO/ * READ
^= TR */READ ^= DMC ^== * ^= GOTO */1
^= TR */1 ^E ## ^== * ^E ^= GOTO */CONV
^= TR */2 ## ^== * ?
Para mí, todo lo que se aleje del lenguaje natural me parece un atraso, cuantos más caracteres “raros”, librerías y ficheros anexos se manejen, más cerca se está de la situación de “cuantos más cables más lio”. Los primeros programas que hice tenían variables formadas con una letra + un número, (A1 = Código de cliente), todo debido a las restricciones físicas. Entiendo que la limitación de recursos obliga a realizar malabarismos, pero en la actualidad hay gente que sigue empeñada en hacer las cosas raras. Cuando leí el primer programa en HTML creía que me habían drogado, me convertí en Segismundo y hablaba con Calderón, afortunadamente era sólo un sueño y “el HTML no existía”. Ahora en serio, creo que Timothy Berners-Lee no lo desarrolló para lo que le estamos utilizando hoy.
Matemáticamente es un algoritmo con la forma: G = (A,P,SP,T), dónde:
G Gramática
A es un alfabeto = {A, B, …, Z}
P Las reglas (Patrón → Reemplazo). Son un conjunto ordenado de pares de palabras de A, cuyos elementos se denominan sustituciones y generalmente se escriben X → y o (X, y) .
SP es un subconjunto de P, cuyos elementos se denominan sustituciones finales.
T es un subconjunto de A, denominado alfabeto terminal.
Ejemplo.
Este sería el funcionamiento básico de un algoritmo:
Conjunto de reglas
- “A” → “DSS”
- “B” → “disco”
- “C” → “formatee”
- “E” → “para “Ester”
- “Ester” → “Ester y Juan José”
- “FX” → “regla de terminación”
Cadena de símbolos.
“Compré un B A y lo C E”
Ejecución
Aplicamos el algoritmo y la cadena de símbolos cambiará según el conjunto de reglas:
- “Compré un B A y lo C E.”
- “Compré un B DSS y lo C E.”
- “Compré un disco DSS y lo C E.”
- “Compré un disco DSS y lo formatee E.”
- “Compré un disco DSS y lo formatee para Ester”.
- “Compré un disco DSS y lo formatee para Ester y Juan Jose”.