Récemment, on m'a rappelé quelques propriétés des machines de Turing (que sont nos ordinateurs, ordiphones, etc.) :
- Le programme et les données sont confondus : rien ne permet de dire, a priori, ce qui est un programme et ce qui est une donnée, tout est 0 et 1. Seule l'interprétation permet de dire ce qui est une donnée ou un programme. Ainsi, il est parfaitement possible d'écouter, avec un lecteur multimédia, un exécutable quelconque : du son sera bien émis ;
- On ne sait pas réduire le jeu d'instructions d'une machine de Turing à la demande. C'est pour cela que les DRM ne peuvent empêcher un ordinateur de copier du contenu, fut-il protégé. C'est aussi pour cela qu'on ne sait pas garantir que tel programme fera toujours uniquement ce que l'on désire, qu'il n'y a pas de fonctions cachées (des bombes logiques) ;
- On ne sait pas prédire, a priori, avant de l'exécuter, la durée d'exécution d'un programme d'une machine de Turing, ni même dire si tel programme destiné à une machine de Turing comporte bien une fin. Je parle de manière générale, pour tout programme, évidemment qu'on sait prédire le comportement d'un « hello world » banal.