Máquina de Moore

En la teoría de la computación , una máquina de Moore es una máquina de estados finitos cuyos valores de salida actuales están determinados únicamente por su estado actual . Esto contrasta con una máquina de Mealy , cuyos valores de salida están determinados tanto por su estado actual como por los valores de sus entradas. Al igual que otras máquinas de estados finitos, en las máquinas de Moore, la entrada suele influir en el siguiente estado. Por lo tanto, la entrada puede influir indirectamente en las salidas subsiguientes, pero no en la salida actual o inmediata. La máquina de Moore recibe su nombre de Edward F. Moore , quien presentó el concepto en un artículo de 1956 titulado « Experimentos mentales sobre máquinas secuenciales». ^{[ 1 ]}

Una máquina de Moore se puede definir como una 6-tupla.${\displaystyle (S,s_{0},\Sigma ,\Lambda ,\delta ,G)}$consta de lo siguiente:

• Un conjunto finito de estados${\displaystyle S}$
• Un estado inicial (también llamado estado de partida)${\displaystyle s_{0}}$que es un elemento de${\displaystyle S}$
• Un conjunto finito llamado alfabeto de entrada${\displaystyle \Sigma }$
• Un conjunto finito llamado alfabeto de salida${\displaystyle \Lambda }$
• Una función de transición${\displaystyle \delta :S\times \Sigma \rightarrow S}$mapear un estado y el alfabeto de entrada al siguiente estado
• Una función de salida${\displaystyle G:S\rightarrow \Lambda }$mapeo de cada estado al alfabeto de salida

La "evolución a través del tiempo" se realiza en esta abstracción haciendo que la máquina de estados consulte el símbolo de entrada que cambia con el tiempo en "pulsos de temporizador" discretos.${\displaystyle t_{0},t_{1},t_{2},...}$y reaccionar de acuerdo con su configuración interna en esos instantes idealizados, o bien hacer que la máquina de estados espere un siguiente símbolo de entrada (como en una FIFO) y reaccione cuando llegue.

Una máquina de Moore puede considerarse un tipo restringido de transductor de estados finitos .

Como las máquinas de Moore y Mealy son ambos tipos de máquinas de estados finitos, son igualmente expresivas: cualquiera de los dos tipos puede utilizarse para analizar un lenguaje regular .

La diferencia entre las máquinas de Moore y las máquinas de Mealy es que en estas últimas, la salida de una transición está determinada por la combinación del estado actual y la entrada actual (${\displaystyle S\times \Sigma }$como dominio de${\displaystyle G}$), en contraposición al estado actual (${\displaystyle S}$como dominio de${\displaystyle G}$). Cuando se representa como un diagrama de estados ,

• En una máquina de Moore, cada nodo (estado) está etiquetado con un valor de salida;
• En una máquina de Mealy, cada arco (transición) está etiquetado con un valor de salida.

Cada máquina de Moore${\displaystyle M}$es equivalente a la máquina de Mealy con los mismos estados y transiciones y la misma función de salida.${\displaystyle G(s,\sigma )=G_{M}(\delta _{M}(s,\sigma ))}$, que toma cada par estado-entrada${\displaystyle (s,\sigma )}$y rendimientos${\displaystyle G_{M}(\delta _{M}(s,\sigma ))}$, dónde${\displaystyle G_{M}}$es${\displaystyle M}$función de salida y${\displaystyle \delta _{M}}$es${\displaystyle M}$función de transición de.

Sin embargo, no todas las máquinas de Mealy se pueden convertir en una máquina de Moore equivalente. Algunas solo se pueden convertir en una máquina de Moore casi equivalente, con las salidas desplazadas en el tiempo. Esto se debe a la forma en que las etiquetas de estado se emparejan con las etiquetas de transición para formar los pares de entrada/salida. Consideremos una transición${\displaystyle s_{i}\rightarrow s_{j}}$del estado${\displaystyle s_{i}}$para declarar${\displaystyle s_{j}}$. La entrada que provoca la transición${\displaystyle s_{i}\rightarrow s_{j}}$etiquetas el borde${\displaystyle (s_{i},s_{j})}$La salida correspondiente a esa entrada es la etiqueta del estado.${\displaystyle s_{i}}$. ^{[ 2 ]} Nótese que este es el estado fuente de la transición. Por lo tanto, para cada entrada, la salida ya está fijada antes de que se reciba la entrada y depende únicamente del estado actual. Esta es la definición original de E. Moore. Es un error común usar la etiqueta de estado${\displaystyle s_{j}}$como resultado de la transición${\displaystyle s_{i}\rightarrow s_{j}}$.

Tipos según el número de entradas/salidas.

Simple

Las máquinas de Moore simples tienen una entrada y una salida:

• Detector de bordes mediante XOR
• máquina sumadora binaria
• Sistemas secuenciales síncronos (una forma restringida de máquina de Moore donde el estado cambia solo cuando cambia la señal de reloj global).

La mayoría de los sistemas electrónicos digitales se diseñan como sistemas secuenciales síncronos . Estos sistemas son una forma restringida de máquina de Moore, donde el estado cambia solo cuando cambia la señal de reloj global. Normalmente, el estado actual se almacena en biestables , y una señal de reloj global se conecta a la entrada de "reloj" de los biestables. Los sistemas secuenciales síncronos son una forma de resolver problemas de metaestabilidad . Una máquina de Moore electrónica típica incluye una cadena lógica combinacional para decodificar el estado actual en las salidas (lambda). En el instante en que cambia el estado actual, esos cambios se propagan a través de la cadena y, casi instantáneamente, la salida se actualiza. Existen técnicas de diseño para asegurar que no se produzcan fallos transitorios en las salidas durante ese breve período mientras los cambios se propagan a través de la cadena, pero la mayoría de los sistemas se diseñan de manera que los fallos transitorios durante ese breve tiempo de transición se ignoren o sean irrelevantes. Las salidas permanecen indefinidamente ( los LED permanecen encendidos, la alimentación de los motores permanece conectada, los solenoides permanecen energizados, etc.) hasta que la máquina de Moore vuelve a cambiar de estado.

Ejemplo resuelto

Una red secuencial tiene una entrada y una salida. La salida se convierte en 1 y permanece en 1 a partir de entonces cuando se han producido al menos dos 0 y dos 1 como entradas.

A la derecha se muestra una máquina de Moore con nueve estados para la descripción anterior. El estado inicial es el estado A, y el estado final es el estado I. La tabla de estados para este ejemplo es la siguiente:

En el artículo de Moore de 1956 " Experimentos mentales sobre máquinas secuenciales", ^{[ 1 ]} el${\displaystyle (n;m;p)}$autómatas (o máquinas)${\displaystyle S}$se definen como tener${\displaystyle n}$estados,${\displaystyle m}$símbolos de entrada y${\displaystyle p}$símbolos de salida. Se demuestran nueve teoremas sobre la estructura de${\displaystyle S}$y experimentos con${\displaystyle S}$. Más tarde, "${\displaystyle S}$Las máquinas que se conocían como "máquinas Moore" pasaron a llamarse "máquinas Moore".

Al final del documento, en la sección "Problemas adicionales", se plantea la siguiente tarea:

Otro problema que se deriva directamente de este es la mejora de las cotas dadas en los teoremas 8 y 9.

El teorema 8 de Moore se formula de la siguiente manera:

Dado un arbitrario${\displaystyle (n;m;p)}$máquina${\displaystyle S}$, de tal manera que cada par de sus estados se distinguen entre sí, entonces existe un experimento de longitud${\displaystyle {\tfrac {n(n-1)}{2}}}$que determina el estado de${\displaystyle S}$al final del experimento.

En 1957, AA Karatsuba demostró los dos teoremas siguientes, que resolvieron completamente el problema de Moore sobre la mejora de los límites de la longitud del experimento de su "Teorema 8".

Teorema A. Si${\displaystyle S}$es un${\displaystyle (n;m;p)}$máquina, de tal manera que cada par de sus estados sean distinguibles entre sí, entonces existe un experimento ramificado de longitud como máximo${\displaystyle {\tfrac {(n-1)(n-2)}{2}}+1}$a través de la cual se puede determinar el estado de${\displaystyle S}$al final del experimento.

Teorema B. Existe un${\displaystyle (n;m;p)}$máquina, cuyos dos estados son distinguibles entre sí, de tal manera que la duración de los experimentos más cortos que establecen el estado de la máquina al final del experimento es igual a${\displaystyle {\tfrac {(n-1)(n-2)}{2}}+1}$.

Los teoremas A y B sirvieron de base para el trabajo de curso de un estudiante de cuarto año, AA Karatsuba, titulado "Sobre un problema de la teoría de autómatas", que fue distinguido con una mención honorífica en el concurso de trabajos estudiantiles de la facultad de mecánica y matemáticas de la Universidad Estatal de Moscú en 1958. El artículo de Karatsuba fue entregado a la revista Uspekhi Mat. Nauk el 17 de diciembre de 1958 y se publicó allí en junio de 1960. ^{[ 3 ]}

Hasta la fecha (2011), el resultado de Karatsuba sobre la duración de los experimentos es el único resultado no lineal exacto, tanto en la teoría de autómatas como en problemas similares de la teoría de la complejidad computacional .

• Circuito síncrono
• Máquina harinosa
• Máquina de estados algorítmica
• Sistema autónomo (matemáticas)

• Conway, JH (1971). Álgebra regular y máquinas finitas . Londres: Chapman and Hall. ISBN 0-412-10620-5. Zbl 0231.94041 . 
• Moore EF Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematics Studies , 34, 129–153. Princeton University Press, Princeton, NJ (1956).
• Karatsuba AA Solución de un problema de la teoría de autómatas finitos. Usp. Mat. Nauk, 15:3, 157–159 (1960).
• Karatsuba AA Experimente mit Automaten (alemán) Elektron. Informaciónverarb. Kybernetik, 11, 611–612 (1975).
• Lista de trabajos de investigación de Karatsuba AA .

Máquina de Moore y Mealy

• Contenido multimedia relacionado con la máquina de Moore en Wikimedia Commons.