Máquina de Post

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 una 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.Uspensky, "A Post Machine" (in Russian), Moscow, "Nauka", 1979.

Enlace externo


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • 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 una autómata determinísta con una cola. No hay cinta de lectura separada. Al principio del cómputo, la cadena de entrada x es… …   Enciclopedia Universal

  • Máquina expendedora — de billetes del Tranvía de Tenerife. Máquina expendedora es una máquina que proporciona aperitivos, bebidas, golosinas y otros productos a los consumidores. Se trata de vender sin la presencia de un dependiente para cobrar los artículos.… …   Wikipedia Español

  • Post mortem (álbum) — Saltar a navegación, búsqueda Post mortem Álbum de Último Resorte Publicación 1994 España Grabación abril de …   Wikipedia Español

  • Post scriptum — Saltar a navegación, búsqueda Post scriptum. Expresión latina que significa después de escrito , abreviado P.S. o PS. Se emplea para añadir algo posterior a un texto, cuando éste ya ha sido dado por concluido, siendo una alternativa a su… …   Wikipedia Español

  • Post scríptum — Post scríptum,[1] del latín post scriptum, es una locución que significa después de escrito , abreviado P. S. o PS. Se emplea para añadir algo posterior a un texto, cuando éste ya ha sido dado por concluido, siendo una alternativa a su corrección …   Wikipedia Español

  • Máquina de registro — En lógica matemática y en ciencias de la computación teórica, una máquina de registro es una clase genérica de máquinas abstractas usadas en una manera similar a una máquina de Turing. Todos los modelos son Turing equivalente. Contenido 1… …   Wikipedia Español

  • Post Office Protocol — POP3 (Post Office Protocol 3). Tercera versión del protocolo diseñado para la gestión, el acceso y la transferencia de mensajes de correo electrónico entre dos máquinas, habitualmente un servidor y una máquina de usuario. Los servidores POP3… …   Enciclopedia Universal

  • Emil Leon Post — Saltar a navegación, búsqueda Emil Leon Post Emil Leon Post (11 de febrero de 1897 en Augustów 21 de abril de 1954 en Nueva York) fue un matemático estadounidense de origen polaco especializado en …   Wikipedia Español

  • Problema de correspondencia de Post — Saltar a navegación, búsqueda El Problema de Correspondencia de Post es un problema de decisión indecidible que fue propuesto por Emil Post. Por ser más sencillo que el Problema de parada y que el Entscheidungsproblem, resulta útil para realizar… …   Wikipedia Español

  • La máquina del tiempo (película de 2002) — Para otros términos similares, véase La máquina del tiempo (desambiguación). The Time Machine Título La máquina del tiempo Ficha técnica Dirección Simon Wells …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”