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
Deterministas y no determinista (software libre).
Datos:Q3267583
Septiembre 10, 2021
máquina, post, teoría, computación, teoría, recursión, máquina, post, bautizada, así, honor, emil, leon, post, autómata, determinista, cola, cinta, lectura, separada, principio, cómputo, cadena, entrada, cargada, cola, cadena, entrada, seguida, símbolo, especi. En teoria de la computacion y teoria de la recursion una maquina de Post bautizada asi en honor de Emil Leon Post es un automata determinista con una cola No hay cinta de lectura separada Al principio del computo la cadena de entrada x es cargada en la cola La cadena de entrada es seguida por un simbolo especial de fin de entrada Al iniciarse el computo la cola solo contiene la configuracion de entrada El primer simbolo de x esta al principio de la cola y el simbolo de final de entrada esta luego del ultimo caracter Una maquina de transicion de Post depende del simbolo al frente de la cola y del estado Cada transicion borrara el simbolo al principio de la cola Una transicion tiene dos componentes el proximo estado y una cadena que se inserta al final de la cola La cadena puede ser vacia Referencias EditarV A Uspenski A Post Machine en ruso Moscu Nauka 1979 Enlaces externos EditarSimulacion de Maquinas de Post Deterministas y no determinista software libre Datos Q3267583Obtenido de https es wikipedia org w index php title Maquina de Post amp oldid 120647727, wikipedia, wiki, leyendo, leer, libro, biblioteca,
