Les machines de Turing
Magazine
Spécialité(s)
Résumé
Y a-t-il des problèmes qu'aucun ordinateur ne pourra jamais résoudre et quels sont-ils ? Pour que les théoriciens puissent répondre à ce type de questions fondamentales, ils bénéficient d'un modèle de calcul à la fois suffisamment puissant pour représenter n'importe quel programme, mais aussi extrêmement simple, ce qui permet de raisonner plus facilement sur les propriétés générales des programmes : la machine de Turing. À travers de nombreux exemples, cet article vous familiarisera avec les machines de Turing et vous donnera quelques-unes de leurs propriétés fondamentales.