Aujourd’hui le nom de Turing est connu des étudiants en informatique puisqu’il est associé à ce qu’on appelle « la machine de Turing ».

Cette « machine » n’a aucunement l’apparence de la machine réellement mécanique construite par Turing pendant la guerre. Il s’agit d’un microprocesseur fictif le plus simple possible. Alors que les microprocesseurs réels actuels sont des « machines à registres spécialisés », la machine virtuelle de Turing est uniquement une machine à pile. Toutes les opérations ramènent à empiler des valeurs et dépiler des résultats pour chaque opération. Cela permet de compter le nombre d’actions élémentaire pour chaque opération et pour chaque algorithme.

Cette machine de Turing est donc utilisée pour évaluer la complexité des algorithmes. Cela n’a absolument rien à voir avec l’Intelligence Artificielle. Il s’agit même, à l’inverse, de tout ce qu’il y a de plus élémentaire en informatique.

L’évaluation de la complexité des algorithmes est nécessaire. Il s’agit d’évaluer le temps nécessaire pour effectuer un calcul en fonction de la taille des données.

La complexité est proportionnelle quand le temps de réalisation est proportionnel à la taille de la donnée. Le temps peut être constant même lorsque la donnée augmente. C’est le cas lorsque vous utilisez des moteurs de recherche qui vous fournissent rapidement des réponses en allant farfouiller dans des données énormes. La complexité peut être algorithmique : le temps augmente moins que la donnée. La complexité peut être exponentielle. On a alors des algorithmes inutilisables, car le résultat n’arrivera que dans quelques millénaires dès que la donnée est grande. Le cas prototypique de complexité exponentielle est celui du « problème du voyageur de commerce » : trouver le circuit le plus cours pour visiter plusieurs villes. Si vous placez quelques centaines de villes, il faut des temps de traitement énormes avec les algorithmes qui développent toute la combinatoire.

Pour faire plus court, je recopie ce que dit très justement Google :

"En informatique théorique, la machine de Turing sert de modèle fondamental pour l’étude de la complexité algorithmique. Elle permet de quantifier les ressources (temps et espace) nécessaires à l’exécution d’un algorithme. La complexité d’un algorithme, exprimée en termes de machine de Turing, représente l’ordre de grandeur du nombre d’opérations élémentaires (lecture, écriture, déplacement de la tête) nécessaires pour résoudre un problème.