Máquina de Post

En teoría de la computación y teoría de la recursión, una máquina de Post, bautizada así en honor de Emil Leon Post, es un autómata determinista con una cola. No hay cinta de lectura separada.

Al principio del cómputo, la cadena de entrada x es cargada en la cola. La cadena de entrada es seguida por un símbolo especial de fin de entrada. Al iniciarse el cómputo, la cola sólo contiene la configuración de entrada. El primer símbolo de x está al principio de la cola y el símbolo de final de entrada está luego del último carácter. Una máquina de transición de Post depende del símbolo al frente de la cola y del estado. Cada transición borrará el símbolo al principio de la cola. Una transición tiene dos componentes: el próximo estado y una cadena que se inserta al final de la cola. La cadena puede ser vacía.

Referencias

• V. A. Uspenski, "A Post Machine" (en ruso), Moscú, "Naúka", 1979.

Enlaces externos

• Simulación de Máquinas de Post Deterministas y no determinista (software libre).

Esta página se editó por última vez el 23 ene 2024 a las 16:21.