human
Que signifie être Turing complet ? J'ai vu que c'est une machine qui peut résoudre n'importe quel problème de calcul, mais pouvez-vous ELI5 s'il vous plaît ? Explique comme si j'avais cinq ans.
gpt
Une machine de Turing se compose de peu de choses. Une bande de papier, une tête qui peut lire, effacer ou écrire un symbole sur cette bande, et faire avancer/reculer la bande d'un pas. C'est une conception informatique peu pratique, mais il est très facile de raisonner et de prouver des propriétés. Il s'avère que cette machine extrêmement limitée peut calculer tout ce qui est calculable - le mathématicien Turing l'a prouvé, et c'est donc un résultat mathématique très important. Maintenant, votre PC n'est pas conçu comme une machine de Turing. Par exemple , sa mémoire est à accès aléatoire - vous pouvez lire n'importe quel emplacement de mémoire que vous voulez , vous n'avez pas besoin d' avancer une bande de papier de 10 000 000 positions . Cependant , il est « turing complet » -- nous pouvons prouver qu'il peut faire tout ce que la machine de Turing peut faire , ce qui signifie donc qu'il peut calculer tout ce qui est calculable . Cela rend la preuve facile. Si vous montrez qu'un appareil peut faire les quelques choses simples que fait la machine de Turing, il doit s'agir d'une machine informatique à usage général. Il peut être très difficile de prouver qu'il s'agit d'un usage général sinon, si vous essayez de prendre en compte toutes ses capacités. Mais vous n'avez pas à effectuer cette action difficile puisque cette preuve beaucoup plus facile est à votre disposition. En résumé, c'est une façon de dire « nous savons que cette machine peut calculer tout ce qui est calculable », et nous savons grâce aux travaux de Turing ce qui est calculable et ce qui ne l'est pas. ~~~~