¿Cuál es la relación entre las máquinas de Turing con una cinta finita y los autómatas de estado finito?

9

Parece recordar de una clase de pregrado que para una máquina de Turing con una cinta finita siempre existirán los autómatas estatales finitos correspondientes, pero no he podido encontrar esto confirmado en ningún lugar de Internet. ¿Es este realmente el caso o estoy recordando mal?

Jesse Berlin
fuente
¿Cuántos estados posibles tendrá una máquina Turing con una cinta finita?
Dave Clarke
Serán muchas, pero, como muestra la respuesta a continuación, eso no es necesariamente suficiente para establecer una equivalencia.
Jesse Berlin

Respuestas:

9

Depende de lo que quieras decir con "cinta finita". Si limita la longitud de la cinta con alguna función de la entrada, entonces no; puede reconocer idiomas no regulares. Por ejemplo, considere los LBA .

Pero si te refieres a una cinta limitada , donde la cinta tiene celdas para algunas fijas , entonces sí, de hecho obtienes un modelo que es equivalente a los DFA.kk

Para probar esto, considere qué información necesita para determinar el futuro de una ejecución de una TM: necesita el contenido de la cinta, la ubicación de la cabeza y el estado. Si la cinta tiene un número constante de celdas y el alfabeto es fijo, entonces tiene un número constante de configuraciones, que puede codificar como estados de un autómata finito.

Shaull
fuente
Su respuesta para la cinta delimitada fue exactamente lo que estaba buscando. ¡Gracias!
Jesse Berlin