Différence entre une machine de Turing et une machine à états finis?

Je fais une présentation sur les machines Turing et je voulais donner quelques informations sur les FSM avant de présenter les machines Turing. Le problème est que je ne sais vraiment pas ce qui est TRÈS différent les uns des autres.

Voici ce que je sais que c'est différent:

FSM a des états séquentiels en fonction de la condition correspondante remplie tandis que les machines Turing fonctionnent sur une "bande" infinie avec une tête qui lit et écrit.

Il y a plus de place pour l'erreur dans les FSM car nous pouvons facilement tomber dans un état sans fin, alors que ce n'est pas tellement pour les machines Turing puisque nous pouvons revenir en arrière et changer les choses.

Mais à part cela, je ne connais pas beaucoup plus de différences qui rendent les machines Turing meilleures que les FSM.

Pouvez-vous m'aider s'il vous plaît?

La principale distinction entre le fonctionnement des DFA (Deterministic Finite Automaton) et des MT réside dans leur utilisation de la mémoire.

Intuitivement, les DFA n'ont aucune mémoire "scratch"; la configuration d'un DFA est entièrement prise en compte par l'état dans lequel il se trouve actuellement et ses progrès actuels dans la lecture de l'entrée.

Intuitivement, les MT ont une mémoire "scratch" sous forme de bande; la configuration d'une MT se compose à la fois de son état actuel et du contenu actuel de la bande, que la MT peut changer à mesure qu'elle s'exécute.

Un DFA peut être considéré comme une MT qui ne modifie aucun symbole de bande ni ne déplace la tête vers la gauche. Ces restrictions rendent impossible la reconnaissance de certaines langues pouvant être acceptées par les MT.

Notez que j'utilise le terme "DFA" plutôt que "FSM", car, techniquement, je considérerais une MT comme une machine à états finis, car les MT ont par définition un nombre fini d'états. La différence entre les DFA et les MT réside dans le nombre de configurations, qui est le même que le nombre d'états pour un DFA, mais est infiniment grand pour une MT.

Les machines de Turing décrivent une classe beaucoup plus large de langages, la classe des langages récursivement énumérables. Les machines à états finis décrivent la classe des langages réguliers.

Les machines à états finis n'ont pas de "mémoire", elle est limitée par ses états.

Une machine à états finis est une machine de Turing restreinte où la tête ne peut effectuer que des opérations de "lecture" et se déplace toujours de gauche à droite.

Prenez cette langue comme exemple:

Parce que les machines à états finis sont limitées dans le sens où elles n'ont pas de mémoire, un FSM qui accepte L ne peut pas être construit.

Résumer:

Les machines à états finis décrivent une petite classe de langages où aucune mémoire n'est nécessaire.

Les machines de Turing sont la description mathématique d'un ordinateur et acceptent une classe de langues beaucoup plus large que les FSM.

Les machines Turing ont plus de puissance de calcul que FSM. Il y a des tâches qu'aucun FSM ne peut faire, mais que les machines de Turing peuvent faire.

J'avais le même doute et j'ai vu deux vidéos très instructives et une explication sur Quora comme suit:

Une machine à états finis n'est qu'un ensemble d'états et de transitions. La seule mémoire dont il dispose est dans quel état il se trouve. Ainsi, le nombre d'états de mémoire est ... fini.

Une machine de Turing est une machine à états finis plus une mémoire à bande. Chaque transition peut être accompagnée d'une opération sur la bande (déplacer, lire, écrire).

J'en ai compris qu'une machine de turing utilise / possède une machine à états finis dans le cadre de sa procédure d'exploitation, en plus d'y ajouter de la mémoire modifiable.

Regardez aussi ces deux vidéos, elles sont éclairantes!

https://youtu.be/gJQTFhkhwPA

https://youtu.be/E3keLeMwfHY

Pour autant que je comprends les différences entre (modèle standard) Turing et (modèle standard) Mealy Machines:

• Machines de Turing lire et écrire sur la même bande par rapport à Mealy Machines lu sur une bande d'entrée et d' écriture sur une autre bande de sortie
• Les machines de Turing peuvent changer la "direction de la bande" (continuer vers la gauche ou la droite [ou arrêter]) contre les machines Mealy ne peuvent procéder que vers la droite (c'est pourquoi il n'y a pas de direction définie {L, R, H} dans la fonction de transition de la machine Mealy [c'est implicitement {R}, ce qui signifie pas de choix du tout])
• Turing Machines peut s'arrêter sur n'importe quelle cellule de bande par rapport à Mealy Machines lire l'entrée complète, puis arrêter de l'accepter ou de la rejeter

Une machine de Turing peut stocker, dans le cadre de la bande, les choses dont elle veut se souvenir.