human
Comment fonctionne une machine de Turing et que fait-elle ? Tout ce que je sais, c'est qu'elle se trouve dans un processeur et qu'elle manipule des données binaires.
gpt
Wikipédia fait un travail décent, donc je vais essayer de simplifier un peu plus (au détriment de l'exactitude). Une machine de Turing n'est *pas* une machine physique (bien que des gens en aient fait). C'est un objet théorique qui sert à modéliser, en quelque sorte, l'ordinateur le plus simple possible. Il reçoit une entrée et peut retourner 'oui' ou 'non' (ou continuer indéfiniment). Un exemple ( et un bon exercice ) consiste à " construire " une machine pour tester si un entier est divisible par 9 . L'entrée serait alors l'entier, et la machine renverrait 'oui' ou 'non' à la fin. Supposons que vous disposiez d'une bande infinie de symboles et d'une « tête », vers laquelle la bande est alimentée, et qui peut être dans différents « états » ou « modes ». A chaque symbole, la tête entreprend une action. Une action pourrait être ' si la tête est dans l'état 1 et si le symbole est un A , effacer le A et écrire B , passer à l'état 2 et se déplacer de trois espaces vers la droite ' , ou ' si la tête est dans l'état 2 et le symbole est un C , retournez oui et quittez ' . Pour tester la divisibilité par neuf, la machine pourrait être la suivante : la bande d'entrée contient le nombre écrit en notation décimale, avec un chiffre par espace. Nous aurions dix états , 0 , 1 , 2 , ... 9 . Les règles seraient : ' commencer à l'état 0 et passer au premier symbole ' , et ' à chaque symbole , ajouter le symbole à l'état actuel et ajouter les chiffres jusqu'à ce que nous ayons un nombre inférieur à 10 , puis déplacer vers la droite d'un espace ' , et ' si nous frappons un espace vide et que nous sommes dans l'état 9 ou 0 , retournez oui . sinon renvoie non ' . Cela utilise l'idée que si la somme des chiffres est divisible par 9 , alors le nombre est divisible par 9 . Essayez ceci avec, disons, 574281 comme entrée pour voir comment la machine fonctionne. Une machine de Turing n'est pas un modèle d'ordinateur réel. Il est cependant théoriquement capable de faire tout ce qu'un vrai ordinateur peut faire. La simplicité des machines de turing par rapport aux ordinateurs réels les rend très utiles pour prouver des choses, car si quelque chose ne peut pas être fait avec une machine de turing, cela ne peut pas être fait avec n'importe quelle machine informatique équivalente. Ils sont également largement utilisés pour l'analyse d'algorithmes. Le nombre « d'actions » prises par la machine est une mesure utile de la rapidité d'un algorithme.