Des limites du calcul… à l’oracle de Turing

Par Rémi Sussan le 17/12/14 

En décembre, le New Scientist a sorti un numéro spécial consacré aux idées scientifiques les plus importantes : au menu, entre autres, le nombre de dimensions, la mécanique quantique, l’infini… et un article nous proposant de réfléchir à la manière de penser la computation. Un texte court et peu détaillé, mais qui a le mérite de pointer dans des directions qui méritent d’être explorées.

En effet, qu’est-ce que la computation ? On ne saurait la limiter aux ordinateurs tels qu’on les connaît. Comme le souligne le New Scientist, on peut calculer avec plein de choses et de beaucoup de manières différentes : avec une abaque on fait déjà de l’informatique. Dans nos colonnes, nous avons plusieurs fois mentionné ces différents modes de calcul, qui ne recourent en rien aux machines telles que nous les connaissons : on peut calculer avec des systèmes collectifs, de l’ADN, et mêmes des animaux comme des crabes. Et ne parlons pas de l’ordinateur quantique…

Dans la question annuelle de The Edge 2014, rappelons que Neil Gershenfeld allait encore plus loin, en affirmant que non seulement les ordinateurs traditionnels ne calculaient pas de la seule manière possible, mais que celle qu’ils employaient constituait un mauvais exemple. Précisons que Neil Gershenfeld, très connu pour avoir formalisé le concept de Fablab, est avant tout un scientifique qui s’est fait remarquer pour son intérêt pour les formes non conventionnelles de computation, tels les ordinateurs à bulle, purement liquides, implémentés dans un milieu microfluidique (vidéo).

Le New Scientist pointe deux aspects de la théorie de la science informatique. L’une concerne les limites des “machines de Turing” et l’autre, l’hypercomputation, traite d’un moyen possible de déplacer ces limites.

Statue d’Alan Turing au Bletchley Park museum

Les limites de la computation

Le problème de l’arrêt est une de ces limites fondamentales. Il démontre qu’il est impossible à un programme de prédire avec certitude quand (et même si) un autre programme va s’arrêter, ayant terminé sa tâche. Cela a l’air très abstrait comme ça, mais ce problème peut avoir des conséquences pratiques et même… fatales, selon l’étude (.pdf) menée par l’éthiciste Matthias Englert, comme nous le rapporte Motherboard. En effet, les dilemmes moraux sont précisément de la classe des problèmes qui restent “indécidables” et où le “calcul ne s’arrête jamais”. Cela pose la question de savoir comment des machines susceptibles de sauver des vies, ou pire, d’en prendre (comme les robots soldats) réagiront face à ces dernier

Lire la suite ...