Pourquoi les machines de Turing à limites linéaires sont-elles plus puissantes que les automates à états finis?

11

J'avais l'impression que nos ordinateurs, étant finis, ne sont finalement pas plus puissants que les machines à états finis (extraordinairement grandes). Cependant, les machines de Turing linéairement délimitées sont également finies, mais il semble que les langues régulières soient strictement un sous-ensemble incorrect de langues contextuelles.

De toute évidence, il me manque quelque chose ici. Que se passe-t-il?

Ben I.
la source

Réponses:

21

La machine de Turing bornée linéaire est limitée à une bande dont la longueur est une fonction linéaire de la longueur de l'entrée.

Si la limite de longueur était constante, la machine ne serait pas plus puissante qu'un DFA. Cependant, un DFA ne peut pas développer plus d'états pour faire face à une entrée plus longue, ce que le LBTM peut faire (en prenant l'état comme étant la configuration de la machine entière). Le LBTM est donc strictement plus puissant.

rici
la source
6
Il y a un résultat intéressant lié à cela. Toute machine Turing qui s'exécute dans l' espace accepte une langue régulière. o(loglogn)
skankhunt42
@ skankhunt42, pourquoi ça?
Ben I.
@ skankhunt42: Corrigez-moi si je me trompe, mais… toute MT qui s'exécute dans l' espace doit s'exécuter dans temps. Mais il n'est pas difficile de montrer que toute MT qui s'exécute en temps décide d'un langage qui peut également être décidé en temps . Ensuite, il y a une constante telle que les premiers caractères de l'entrée déterminent si l'entrée est dans la langue. Mais alors le langage est évidemment régulier: il suffit d'inclure un état pour chaque préfixe dans . Suis-je en train de manquer quelque chose? Où est mon erreur? kloglogn2kloglogn=2log(logkn)=logkno(n)O(1)cNc0ic{0,1}i
wchargin
@Choirbean Il nécessite une preuve utilisant des séquences croisées. Vous pouvez le rechercher ici cs.stackexchange.com/questions/7372/… .
skankhunt42
@wchargin Je pense que l'erreur pourrait être de prétendre que la MT s'exécute en fois car vous devez également tenir compte de la position de la tête de la bande d'entrée tout en comptant le nombre de configurations. Donc, je pense que la MT s'exécute dans le temps . 2kloglognn2kloglogn
skankhunt42
4

Je pense que nous devons d'abord comprendre la description d'une machine et la taille d'entrée, afin que la comparaison ne porte que sur des objets valides. Disons que N est une taille d'entrée. Cela signifie que les machines auront ces limites de ressources.

ResourceFinite Automata:ALBTM:MInput Tape SizeO(N)O(N)Tape OperationsRead OnlyRead, WriteTape MovementLeft to right, One pass onlyBoth directions, No pass limit# of Locations (States)MMInput AlphabetΣΣAcceptance ConditionReach finite location: fReach finite location: f

Maintenant, est plus expressif que . C'est simplement parce que le mouvement et les restrictions de la bande sont limités pour .MAA

Faisons maintenant une comparaison invalide .

ResourceFinite Automata:ALBTM:MInput Tape SizeO(N)O(N)Tape OperationsRead OnlyRead, WriteTape MovementLeft to right, One pass onlyBoth directions, No pass limit# of Locations (States)M×2NMInput AlphabetΣΣAcceptance ConditionReach finite location: fReach finite location: f

Ici et ont le même pouvoir expressif. Mais, notez que la taille de dépend de l'entrée de manière exponentielle. Taille antérieure de ne dépend pas de . Cela signifie que pour chaque entrée de , vous devrez générer de nouveaux FA, même si reste inchangé.M A N A N M MAMANANMM

Devendra Bhave
la source