Fiche de révision : Programmes et données

Machines de Turing

• Les premiers algorithmes remontent à l'Antiquité.
• Les premières machines à calculer sont apparues au XVII^e siècle.
• Le concept de programme informatique est apparu au XIX^e siècle.
• Dans les années 1930, cherchant à formaliser ce qui caractérise fondamentalement le calcul, Alan Turing réfléchit à une logique générale qui pourrait s'appliquer à tous les calcul.
• Il va pour cela inventer une machine abstraite (la « machine de Turing ») capable d’appliquer une logique générale pouvant s’appliquer à tous les calculs.
• Il imagine sa machine calculante dotée de différents composants :
• un ruban ;
• un pointeur mobile ;
• une table de transitions.
• La table de transitions est composée d'une série d'instructions : elle constitue le programme qui va s'appliquer aux données présentes sur le ruban, et ainsi permettre d'effectuer le calcul désiré en un nombre fini d'opérations.
• La table de transitions indique les actions à mener, en fonction de l'état interne du pointeur et du contenu de la case courante du ruban.
• Ces actions consistent en l'écriture d'une valeur sur le ruban, puis en un déplacement ou l'arrêt de la machine.
• Alan Turing avait également imaginé un concept de machine universelle qui aurait la particularité de pouvoir simuler le fonctionnement de n'importe quelle autre machine de Turing.
• Si on transpose ce concept aux ordinateurs modernes, ils ont globalement les possibilités de calcul d'une machine de Turing universelle (à ceci près que leur mémoire, bien que considérable, n’est pas infinie).
• Un problème est calculable s'il est traitable par une machine de Turing. Church et Turing se rejoignent ainsi dans leurs recherches sur les limites de ce qui est calculable et de ce qui ne l'est pas.
• Pour déterminer si tout est ou non calculable, Church et Turing ont chacun recherché et trouvé l'existence d'un problème qu'il ne serait pas possible de résoudre par un algorithme : il s'agit du problème de l’arrêt.

Le problème de l'arrêt

• La problématique de la décidabilité est équivalente à celle de la calculabilité.
• Un problème est dit « décidable » s'il existe un algorithme qui permet de le résoudre.
• A contrario, un problème est dit « indécidable » s'il n'existe pas d'algorithme qui permette de le résoudre.
• La question posée par Turing peut se présenter ainsi : existe-t-il une machine de Turing capable de déterminer si une machine de Turing quelconque finira par s'arrêter ou si au contraire elle continuera de boucler de manière infinie ?
• Il suffit de trouver un seul cas mettant en échec ce principe pour prouver qu'un tel programme ne peut pas exister.
• Il s'agit d'une démonstration par l'absurde : on suppose que ce problème de l'arrêt est décidable, c'est-à-dire qu'il existe une méthode générale pour savoir si une machine va s'arrêter ou pas sur une entrée donnée.
• Il est possible d’effectuer une démonstration supposant plusieurs machines aux fonctionnement variés (cf. fiche de cours).
• Il est aussi possible d'effectuer la démonstration avec un programme (cf. fiche de cours).
• Il n'existe pas d'algorithme qui permette de résoudre ce problème : le problème de l'arrêt est donc indécidable.
• L'indécidabilité du problème de l'arrêt a permis à Church et Turing de montrer que tout n'était pas calculable.
• Même si leurs travaux étaient mathématiques, ils ont eu une grande influence sur la conception ultérieure des machines que seront les ordinateurs.
• Examinons maintenant nos programmes informatiques modernes et les données qu'ils traitent sous l'angle des machines de Turing.

Programmes et données

• Tout ce qui peut être calculé par une machine de Turing peut l'être par un ordinateur.
• Et logiquement, ce qu'une machine de Turing ne peut pas calculer ne peut pas non plus l'être par un ordinateur.
• Ainsi, les machines de Turing traitent des tables de transitions appliquées à des données, comme nos ordinateurs exécutent des programmes traitant des données :
• un programme est une implémentation d'un algorithme de traitement de données ;
• une donnée est une information ou un ensemble d'informations traitées par un programme.
• La fonction ci-dessous indique si un nombre est pair ou impair.
  def est_pair(nombre) :

• La fonction définit un algorithme (programme) capable d'évaluer des données (nombres) passées en arguments lors des appels de la fonction.
• Le code définissant cette fonction est lui-même exprimé sous forme de texte interprétable par le langage Python.
• La même logique s'applique au code source d'un langage compilé afin de produire un programme exécutable.
• Lorsqu’un logiciel est téléchargé, il est transféré sous forme d’octets (données de téléchargement).
• Son stockage sur la machine locale s'effectue sous forme de données enregistrées et gérées par le système d'exploitation.
• Lorsqu'il est exécuté, cet ensemble de données est un programme qui peut lui-même recevoir, transformer et produire des données.
• Ces différentes illustrations montrent qu'en fonction du contexte, un même élément peut être soit un programme, soit un ensemble de données, ainsi que nous l'avions abordé de manière plus abstraite avec les machines de Turing.