Parece que me lembro de uma turma de graduação que, para uma Máquina de Turing com fita finita, sempre existirá um Autômato de Estado Finito correspondente, mas não consegui encontrar isso confirmado em nenhum lugar da Internet. Este é realmente o caso ou estou me lembrando errado?
turing-machines
finite-automata
Jesse Berlin
fonte
fonte
Respostas:
Depende do que você quer dizer com "fita finita". Se você limitou o comprimento da fita por alguma função da entrada, então não - você pode reconhecer idiomas não regulares. Por exemplo, considere os LBAs .
Para provar isso, considere as informações necessárias para determinar o futuro de uma execução de uma TM: você precisa do conteúdo da fita, da localização do cabeçote e do estado. Se a fita possui um número constante de células e o alfabeto é fixo, você tem um número constante de configurações, que podem ser codificadas como estados de um autômato finito.
fonte