En ciencias de la computación , un historial de computación es una secuencia de pasos dados por una máquina abstracta en el proceso de computar su resultado. Las historias de computación se utilizan con frecuencia en pruebas sobre las capacidades de ciertas máquinas y, en particular, sobre la indecidibilidad de varios lenguajes formales .
Formalmente, un historial de computación es una secuencia (normalmente finita ) de configuraciones de un autómata formal . Cada configuración describe completamente el estado de la máquina en un punto particular. Para ser válido, ciertas condiciones deben cumplir:
- la primera configuración debe ser una configuración inicial válida del autómata y
- cada transición entre configuraciones adyacentes debe ser válida de acuerdo con las reglas de transición del autómata.
Además, para estar completo , un historial de cálculo debe ser finito y
- la configuración final debe ser una configuración terminal válida del autómata.
Las definiciones de "configuración inicial válida", "transición válida" y "configuración de terminal válida" varían para diferentes tipos de máquinas formales.
Un autómata determinista tiene exactamente un historial de cálculo para una configuración inicial dada, aunque el historial puede ser infinito y, por lo tanto, incompleto.
Máquinas de estado finito
Para una máquina de estados finitos , una configuración es simplemente el estado actual de la máquina, junto con la entrada restante. La primera configuración debe ser el estado inicial dey la entrada completa. Una transición de una configuración a una configuración está permitido si para algún símbolo de entrada y si tiene una transición de a en la entrada . La configuración final debe tener la cadena vacíacomo su entrada restante; ya seaha aceptado o rechazado la entrada depende de si el estado final es un estado de aceptación. [1]
Máquinas de Turing
Las historias de computación se usan más comúnmente en referencia a las máquinas de Turing . La configuración de una máquina de Turing de una sola cinta consta del contenido de la cinta, la posición del cabezal de lectura / escritura en la cinta y el estado actual de la máquina de estado asociada; esto suele estar escrito
dónde es el estado actual de la máquina, representado de alguna manera que se distingue del lenguaje de la cinta, y donde se coloca inmediatamente antes de la posición del cabezal de lectura / escritura.
Considere una máquina de Turing en la entrada . La primera configuración debe ser, dónde es el estado inicial de la máquina de Turing. El estado de la máquina en la configuración final debe ser (el estado de aceptación) o (el estado de rechazo). Una configuración es un sucesor válido de la configuración si hay una transición del estado en al estado en que manipula la cinta y mueve el cabezal de lectura / escritura de una manera que produce el resultado en . [2]
Resultados de decidibilidad
Los historiales de computación pueden usarse para mostrar que ciertos problemas de los autómatas de empuje son indecidibles . Esto se debe a que el lenguaje de los historiales de computación que no aceptan de una máquina de Turing en la entrada es un lenguaje libre de contexto reconocible por un autómata pushdown no determinista.
Codificamos un historial de computación de Turing como la cuerda , dónde es la codificación de la configuración , como se discutió anteriormente, y donde todas las demás configuraciones se escriben al revés. Antes de leer una configuración en particular, el autómata pushdown hace una elección no determinista para ignorar la configuración o leerla completamente en la pila.
- Si el autómata pushdown decide ignorar la configuración, simplemente la lee y la descarta por completo y hace la misma elección para la siguiente.
- Si decide procesar la configuración, la inserta completamente en la pila y luego verifica que la siguiente configuración sea una sucesora válida de acuerdo con las reglas de . Dado que las configuraciones sucesivas siempre se escriben en órdenes opuestos, esto se puede hacer, para cada símbolo de cinta en la nueva configuración, sacando un símbolo de la pila y verificando si son iguales. Donde no estén de acuerdo, debe ser responsable por una transición válida de. Si, en cualquier momento, el autómata decide que la transición no es válida, inmediatamente entra en un estado de aceptación especial que ignora el resto de la entrada y acepta al final.
Además, el autómata verifica que la primera configuración sea la configuración inicial correcta (si no, acepta) y que el estado de la configuración final del historial es el estado de aceptar (si no, acepta). Dado que un autómata no determinista acepta si hay alguna forma válida de aceptar, el autómata descrito aquí descubrirá si el historial no es un historial de aceptación válido y aceptará si es así, y rechazará si no. [3]
Este mismo truco no se puede utilizar para reconocer la aceptación de historiales de cálculo con un NPDA, ya que el no determinismo podría utilizarse para omitir una prueba que, de otro modo, fallaría. Una máquina de Turing de límites lineales es suficiente para reconocer los historiales de cómputo aceptables.
Este resultado nos permite demostrar que , el lenguaje de los autómatas pushdown que aceptan todas las entradas, es indecidible. Supongamos que tenemos un decisor para ello,. Para cualquier máquina de Turing y entrada , podemos formar el autómata de empuje que acepta historiales de cálculo no aceptables para esa máquina. aceptará si y solo si no hay historiales de cómputo aceptables para en ; esto nos permitiría decidir, que sabemos que es indecidible.
Ver también
Referencias
- ^ Christine L. Mumford; Lakhmi C. Jain (2009). Inteligencia Computacional: Colaboración, Fusión y Emergencia . Saltador. pag. 337. ISBN 978-3-642-01798-8. Consultado el 25 de marzo de 2012 .
- ^ Andreas Blass (22 de octubre de 2010). Campos de la lógica y la computación: ensayos dedicados a Yuri Gurevich con motivo de su 70 cumpleaños . Saltador. pag. 468. ISBN 978-3-642-15024-1. Consultado el 25 de marzo de 2012 .
- ^ Lenore Blum (1998). Complejidad y computación real . Saltador. pag. 31 . ISBN 978-0-387-98281-6.