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?
turing-machines
finite-automata
Jesse Berlin
fuente
fuente
Respuestas:
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.k k
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.
fuente