Historia de cómputo

En ciencias de la computación, una historia de cómputo es una secuencia de pasos dados por una máquina abstracta en el proceso de cálculo de su resultado. Historias de cómputo se utilizan frecuentemente en pruebas sobre las capacidades de ciertas máquinas, y en particular acerca de la indecidibilidad de diversos lenguajes formales.

Formalmente, una historia de cómputo es una (normalmente finita) secuencia 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álida, ciertas condiciones deben cumplirse:

• La primera configuración tiene que ser una configuración inicial válida del autómata y
• Cada transición entre configuraciones adyacentes tiene que ser válida según las reglas de transición del autómata.

Además, para ser completo, una historia de cómputo tiene que ser finita y

• La configuración final tiene que ser una configuración terminal válida del autómata.

Las definiciones de "configuración inicial válida", "transición válida", y "la configuración terminal válida" varían para diferentes clases de máquinas formales.

Un autómata determinista tiene exactamente una historia de cómputo para una configuración inicial dada, aunque la historia puede ser infinita y por lo tanto incompleta.

Máquinas de estado finito

Para una máquina de estado finito $M$, 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 de $M$ y la entrada completa. Una transición de una configuración $(S,I)$ a una configuración $(T,J)$ se permite si $I=aJ$ para algún símbolo de entrada $a$ y si $M$ tiene una transición de $S$ a $T$ con la entrada $a$. La configuración final debe tener la cadena vacía $\epsilon$ como su entrada restante; si $M$ ha aceptado o rechazado la entrada depende de si el estado final es un estado de aceptación.​

Máquinas de Turing

Las historias de cómputo se usan más comúnmente en referencia a las Máquinas de Turing. La configuración de una sola cinta de la máquina de Turing consta de los contenidos de la cinta, la posición de la cabeza de lectura / escritura en la cinta, y el estado actual de la máquina de estado asociado; esto se suele escribir

$...0011010101q00110101010...$

dónde $q$ es el estado actual de la máquina, representado de alguna manera que es distinguible por el lenguaje de la cinta, y dónde $q$ se coloca inmediatamente antes de la posición de la cabeza de lectura / escritura.

Considere una máquina de Turing $M$ con entrada $w$. La primera configuración debe ser $q_{0}w_{0}w_{1}...$ , dónde $q_{0}$ es el estado inicial de la máquina de Turing. El estado de la máquina en la configuración final debe ser $q_{a}$ (el estado a aceptar) o $q_{r}$ (el estado a rechazar). Una configuración$c_{i+1}$ es un sucesor válido de la configuración $c_{i}$ si hay una transición desde el estado $c_{i}$ al estado $c_{i+1}$ que manipula la cinta y mueve la cabeza de lectura / escritura de una manera que produce el resultado en $c_{i+1}$​

Resultados de decidibilidad

Las historias de cómputo se pueden utilizar para mostrar que ciertos problemas para los autómatas de pila son indecidibles. Esto es porque el lenguaje que no acepta historias de cómputo de una Máquina de Turing $M$ con entrada $w$ es un lenguaje libre de contexto reconocible por un autómata de pila no determinista.

Codificamos una historia de cómputo de Turing $c_{0},c_{1},...,c_{n}$ como la cadena$C_{0}\#C_{1}^{r}\#C_{2}\#C_{3}^{r}\#...\#C_{n}$, donde $C_{i}$ es la codificación de la configuración $c_{i}$, como se discutió anteriormente, y donde cada otra configuración se escribe al revés. Antes de leer una configuración particular, el autómata de pila hace una elección no determinista para ignorar la configuración o leerla en su totalidad en la pila.

• Si el autómata de pila decide ignorar la configuración, simplemente lee y descarta por completo y hace la misma opción para la siguiente.
• Si se decide procesar la configuración, la coloca por completo en la pila, a continuación, verifica que la siguiente configuración es un sucesor válido de acuerdo a las reglas de $M$. Desde entonces las sucesivas configuraciones siempre se escriben en órdenes opuestos, esto se puede hacer porque, por cada símbolo de la cinta en la nueva configuración, saca fuera un símbolo de la pila y comprueba si es la misma. Cuando no coinciden, debe ser a causa de una transición válida de $M$. Si, en cualquier punto, el autómata decide que la transición es nula, inmediatamente introduce un estado especial de aceptación el cual ignora el resto de la entrada y acepta al final.

Además, el autómata verifica que la primera configuración es la configuración inicial correcta (si no, acepta) y que el estado de la configuración final de la historia es el estado a aceptar (si no, acepta). Desde entonces un autómata no determinista acepta si hay alguna manera válida para que acepte, el autómata que se describe aquí descubrirá si la historia no es una historia de aceptación válida y aceptará si es así, y rechazará en caso contrario.​

Este mismo truco no se puede utilizar para reconocer la aceptación de historias de cómputo con un NPDA, ya que el no determinismo podría ser utilizado para saltar una prueba que de otro modo fallaría. Una máquina de Turing lineal acotada es suficiente para reconocer la aceptación de las historias de cómputo.

Este resultado nos permite demostrar que $ALL_{PDA}$, el lenguaje de autómatas de pila que acepta todas las entradas, es indecidible. Supongamos que tenemos una solución para esto, $D$. Para cualquier máquina de Turing$M$ y entrada $w$, podemos formar el autómata de pila $P$ que acepta historias de cómputo no aceptables para esa máquina. $D(P)$ aceptará si y sólo si no hay historias de cómputo aceptables para $M$ en $w$; esto permitiría que tomáramos una decisión de $A_{TM}$ , que sabemos que es indecidible.

Referencias

• Datos: Q5157272