Il me semble me rappeler dans une classe de premier cycle que pour une machine de Turing avec une bande finie, il existera toujours un automate d'état fini correspondant, mais je n'ai pu le trouver confirmé nulle part sur Internet. Est-ce vraiment le cas ou est-ce que je me souviens mal?
turing-machines
finite-automata
Jesse Berlin
la source
la source
Réponses:
Cela dépend de ce que vous entendez par «bande finie». Si vous limitez la longueur de la bande par une fonction de l'entrée, alors non - vous pouvez reconnaître des langues non régulières. Par exemple, considérez les LBA .
Pour le prouver, considérez les informations dont vous avez besoin pour déterminer l'avenir d'une série de MT: vous avez besoin du contenu de la bande, de l'emplacement de la tête et de l'état. Si la bande a un nombre constant de cellules et que l'alphabet est fixe, vous disposez d'un nombre constant de configurations, que vous pouvez encoder en tant qu'états d'un automate fini.
la source