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
Une machine de Turing n'est *pas* dans un CPU et elle ne manipule *pas* de données binaires. Il est important de ne pas commencer avec de fausses suppositions, je pense. :-) Une machine de Turing ressemble plus à un jeu basé sur des règles qu'à un jouet physique. Pensez-y comme le jeu Solitaire . Vous commencez avec un jeu de cartes mélangées et vous les disposez selon les règles du jeu. C'est une partie de la machine de Turing, que nous appelons l'entrée. La partie suivante de la machine de Turing est l'état final --- cela décrit les conditions lorsque le jeu est terminé. Au Solitaire, vous gagnez en plaçant toutes vos cartes dans des colonnes ordonnées numériques ; et vous perdez en parcourant toutes vos cartes sans y parvenir, vous n'avez donc plus d'options. La troisième partie importante de la machine de Turing est la règle du jeu : à chaque étape, elle vous indique quels coups vous pouvez effectuer. Dans certains types de jeu, il y a plusieurs mouvements que vous pouvez faire à chaque étape, et c'est au joueur de choisir. D'autres n'ont pas le choix et le plaisir du jeu vient du fait qu'il se déroule devant vous même si vous ne pouvez pas affecter le résultat. La machine de Turing a été inventée pour formaliser la notion de règles et de processus. La question à laquelle Alan Turing voulait répondre concernait la « partie finale ». Est-il possible de savoir si vous gagnerez une partie de Solitaire sans jouer au Solitaire ? Pourriez-vous être coincé dans une boucle sans fin s'il n'y avait aucun moyen de perdre, seulement de gagner ? En répondant à cette question, il s'est rendu compte qu'il pouvait écrire chacune de ses machines de Turing sous la forme d'un groupement de symboles, comme {entrée, règles, conditions de fin} et ce serait une définition complète de cette machine de Turing. Ce serait la définition formelle ultime du Solitaire, ou quoi que ce soit d'autre. Mais une fois que vous avez une définition d'une machine de Turing comme une série de symboles, vous pouvez la transmettre à une machine de Turing dont les règles lui disent comment reconnaître les symboles. Disons donc que j'ai une machine de Turing appelée SolTM = { deck d' entrée , règles de Solitaire , conditions de fin } . Et j'en ai un nouveau appelé UTM = { input TM , rules , end conditions } . Si je manipule SolTM en utilisant les règles définies dans UTM, je fais en sorte que l'UTM _ agisse comme SolTM _ . C'est l'essence de la _Universal Turing Machine_ d'Alan Turing, un appareil qui peut prétendre être d'autres appareils si on leur donne une description de leur fonctionnement. J'apprécie que ce soit peut-être des trucs assez poilus, et au-dessus de la tête de la plupart des jeunes de 25 ans :-) mais c'est aussi les fondements de notre compréhension du calcul, c'est-à-dire la question de produire "mécaniquement" une sortie à partir d'entrées + règles .