algoritmo de Markov

En informática teórica , un algoritmo de Markov es un sistema de reescritura de cadenas que utiliza reglas gramaticales para operar con cadenas de símbolos. Se ha demostrado que los algoritmos de Markov son Turing-completos , lo que significa que son adecuados como modelo general de computación y pueden representar cualquier expresión matemática a partir de su notación simple. Los algoritmos de Markov reciben su nombre del matemático soviético Andrey Markov Jr.

Refal es un lenguaje de programación basado en algoritmos de Markov.

Los algoritmos normales son verbales, es decir, están diseñados para aplicarse a cadenas de caracteres en diferentes alfabetos.

La definición de cualquier algoritmo normal consta de dos partes: un alfabeto , que es un conjunto de símbolos, y un esquema . El algoritmo se aplica a cadenas de símbolos del alfabeto. El esquema es un conjunto finito y ordenado de fórmulas de sustitución . Cada fórmula puede ser simple o final . Las fórmulas de sustitución simples se representan mediante cadenas de la forma${\displaystyle L\to D}$, dónde${\displaystyle L}$y${\displaystyle D}$son dos cadenas arbitrarias del alfabeto. De manera similar, las fórmulas de sustitución final se representan mediante cadenas de la forma${\displaystyle L\to \cdot D}$.

Aquí hay un ejemplo de un esquema de algoritmo normal en el alfabeto de cinco letras.${\displaystyle |*abc}$:

${\displaystyle \left\{{\begin{matrix}|b&\to &ba|\\ab&\to &ba\\b&\to &\\{*}|&\to &b*&\\{*}&\to &c&\\|c&\to &c\\ac&\to &c|\\c&\to \cdot \end{matrix}}\right.}$

El proceso de aplicar el algoritmo normal a una cadena arbitraria${\displaystyle V}$En el alfabeto de este algoritmo hay una secuencia discreta de pasos elementales, que consiste en lo siguiente. Supongamos que${\displaystyle V'}$es la palabra obtenida en el paso anterior del algoritmo (o la palabra original)${\displaystyle V}$, si el paso actual es el primero). Si de las fórmulas de sustitución no hay un lado izquierdo que esté incluido en el${\displaystyle V'}$, entonces el algoritmo termina y el resultado de su trabajo se considera la cadena${\displaystyle V'}$. De lo contrario, la primera de las fórmulas de sustitución cuyos lados izquierdos están incluidos en${\displaystyle V'}$se selecciona. Si la fórmula de sustitución es de la forma${\displaystyle L\to \cdot D}$, entonces de entre todas las posibles representaciones de la cadena${\displaystyle V'}$de la forma${\displaystyle RLS}$(dónde${\displaystyle R}$y${\displaystyle S}$son cadenas arbitrarias) la que tiene la más corta${\displaystyle R}$se elige. Luego el algoritmo termina y el resultado de su trabajo se considera que es${\displaystyle RDS}$Sin embargo, si esta fórmula de sustitución es de la forma${\displaystyle L\to D}$, entonces de entre todas las posibles representaciones de la cadena${\displaystyle V'}$de la forma de${\displaystyle RLS}$el que tiene el más corto${\displaystyle R}$Se elige, después de lo cual la cadena${\displaystyle RDS}$se considera el resultado del paso actual, sujeto a procesamiento adicional en el siguiente paso.

Por ejemplo, el proceso de aplicar el algoritmo descrito anteriormente a la palabra${\displaystyle |*||}$da como resultado la secuencia de palabras${\displaystyle |b*|}$,${\displaystyle ba|*|}$,${\displaystyle a|*|}$,${\displaystyle a|b*}$,${\displaystyle aba|*}$,${\displaystyle baa|*}$,${\displaystyle aa|*}$,${\displaystyle aa|c}$,${\displaystyle aac}$,${\displaystyle ac|}$y${\displaystyle c||}$, después de lo cual el algoritmo se detiene con el resultado${\displaystyle ||}$.

Para ver otros ejemplos, consulte a continuación.

Cualquier algoritmo normal es equivalente a alguna máquina de Turing , y viceversa : cualquier máquina de Turing es equivalente a algún algoritmo normal. Una versión de la tesis de Church-Turing formulada en relación con el algoritmo normal se denomina «principio de normalización». 

Los algoritmos normales han demostrado ser un medio conveniente para la construcción de muchas secciones de las matemáticas constructivas . Además, la definición de un algoritmo normal implica una serie de ideas utilizadas en lenguajes de programación destinados a manejar información simbólica , por ejemplo, en Refal . 

Las reglas son una secuencia de pares de cadenas, generalmente presentadas en forma de patrón → reemplazo . Cada regla puede ser ordinaria o terminante.

Dada una cadena de entrada :

1. Comprueba las reglas en orden, de arriba abajo, para ver si alguno de los patrones se encuentra en la cadena de entrada .
2. Si no se encuentra ninguno, el algoritmo se detiene.
3. Si se encuentra uno (o más), utilice el primero de ellos para reemplazar la aparición más a la izquierda del texto coincidente en la cadena de entrada con su reemplazo .
4. Si la regla que se acaba de aplicar es una regla de terminación, el algoritmo se detiene.
5. Ve al paso 1.

Tenga en cuenta que después de aplicar cada regla, la búsqueda vuelve a empezar desde la primera regla.

El siguiente ejemplo muestra el funcionamiento básico de un algoritmo de Markov.

Estas reglas ofrecen un ejemplo más interesante. Reescriben los números binarios a sus equivalentes unarios. Por ejemplo, el 101 se reescribe como una secuencia de 5 barras consecutivas.

• Gramática formal

• Caracciolo di Forino, A. Lenguajes de procesamiento de cadenas y algoritmos de Markov generalizados. En Lenguajes y técnicas de manipulación de símbolos, DG Bobrow (Ed.), North-Holland Publ. Co., Ámsterdam, Países Bajos, 1968, pp.  191–206.
• Andrey Andreevich Markov (1903–1979) 1960. La teoría de los algoritmos. Traducciones de la Sociedad Matemática Americana, serie 2, 15, 1–14. (Traducción del ruso, Trudy Instituta im. Steklova 38 (1951) 176-189 ^{[ 1 ]} )

• Yad Studio - Entorno de desarrollo integrado (IDE) e intérprete de algoritmos de Markov (Código abierto)
• Intérprete del algoritmo de Markov
• Intérprete del algoritmo de Markov
• Intérpretes de algoritmos de Markov en Rosetta-Code
• A=B, un juego sobre cómo escribir reglas de sustitución para un algoritmo de Markov.