Biologie Informatique Non classé Sciences

Les bactéries sont-elles capables de penser ?

Je rebondis sur les commentaires du billet précédent, et sur la pertinence de l’analogie entre informatique et biologie. David Bikard affirme notamment :

En revanche il est tout à fait raisonnable de considérer une cellule comme une machine de Turing parallèle et capable de se reproduire. La comparaison avec l’informatique vient de là.

L’occasion d’une petite réflexion (peut-être fausse).

Dans les années 40, Schrodinger a publié un tout petit opuscule, intitulé « qu’est-ce que la vie », dans lequel il s’interrogeait sur les propriétés physiques du vivant (je vous renvoie à ma fiche de lecture). La réflexion de Schrodinger repose sur le constat que les fluctuations thermiques à petite échelle devraient représenter de considérables difficultés pour que les cellules puissent se reproduire correctement. Il en déduit qu’au coeur des cellules doit exister un cristal, très stable, pouvant ainsi se transmettre de générations en générations. En d’autres termes, Schrodinger a en quelque sorte prédit l’existence d’une molécule semblable à l’ADN.
Mais Schrodinger généralise sa conclusion (je m’autocite) :

Comment un objet physique peut-il lui aussi échapper aux fluctuations statistiques, à la thermodynamique ? Schrodinger invoque une loi de la physique parfois appelée le “troisième principe de la thermodynamique”, le principe de Nernst. Ce principe relie l’augmentation d’entropie (second principe de la thermodynamique) à la température. Plus la température diminue, moins l’augmentation d’entropie d’un système isolé au cours du temps est importante. Lorsque le zéro absolu est atteint, l’entropie n’augmente plus et le degré d’ordre d’un objet physique ne diminue plus avec le temps. Schrodinger souligne alors qu’une température proche du zero absolu peut être en réalité assez élevée en fonction du système considéré. Prenez l’exemple d’un pendule oscillant : il peut osciller très longtemps régulièrement sans être influencé par les fluctuations thermiques de la pièce où il se trouve (…) Pour Schrodinger, le vivant n’est capable de maintenir son ordre que parce qu’il n’est pas très différent d’un système mécanique et que ses constituants fondamentaux travaillent “effectivement” à température nulle.

Seulement Schrodinger voit bien les limites de cette vision. Si la vie est pure mécanique, comment expliquer le libre-arbitre ?

Cette question rejoint en fait directement les interrogations philosophiques d’Alan Turing (dont j’avais dressé le portrait il y a quelques mois). Turing a inventé ces fameuses machines pour résoudre le problème 10 de la fameuse liste de Hilbert. Il a ainsi défini proprement la notion d’algorithme. Il a montré en particulier qu’il y a des problèmes qui ne peuvent être résolus par des algorithmes, des problèmes indécidables, comme le problème dit de l’arrêt.

Pour résoudre ces problèmes, Turing a proposé l’existence d' »oracles » extérieurs aux machines. Certains scientifiques pensent que ces « oracles » sont nécessaires pour simuler la pensée et donc résoudre le problème du libre-arbitre associé pour les machines :

Cet « oracle » est un élément irrationnel proche d’une « intuition ». L’origine, ou la nécessité logique de ces « oracles » est dans le fait qu’un certain nombre de problèmes sont connus pour ne pas être calculables; par ailleurs, tout système formel est limité par le théorème de Gödel qui suppose l’existence de propositions indémontrables à l’intérieur du système. Or, chacun reconnaît que l’homme est capable de considérer le théorème de Gödel, en quelque sorte de l’extérieur, et contemple sans embarras les impossibilités logiques impliquées par le théorème, qu’il lève aussitôt par l’exercice de son libre arbitre.

(extrait du texte sur Turing publié par V. Fleury dans la revue Sigila que j’avais lié dans ce billet).

La question que je me pose est la suivante : les bactéries prennent-elles des décisions comme des machines de Turing, i.e. suivent-elles un algorithme ? Ou au contraire les bactéries « invoquent »-elles parfois un oracle ?

En fait, on rejoint la théorie de Schrodinger, qui se trompe partiellement. Les bactéries ne sont pas de pures machines, elles ne suivent pas individuellement un algorithme déterministe par définition. Si on lance le même programme sur le même ordinateur, il vaut mieux qu’on trouve le même résultat. Il en est tout autre pour les bactéries :  en réalité les fluctuations thermiques ont un rôle, et, mieux, sont exploitées par les bactéries. L’un des exemples les plus frappants est constitué par les phénomènes de variabilité phénotypique, dont j’avais parlé dans ce billet. Les bactéries sont capables de changer de phénotype de façon totalement aléatoire, elles sont donc capables en quelque sorte de prendre des décisions sans raison, en utilisant le bruit thermique, et cette faculté de prendre des décisions a été qui plus est sélectionnée par l’évolution. Serait-ce un oracle à la Turing ?

Plus généralement, qu’on songe au processus d’évolution même. Ce n’est pas un processus purement mécanique ou algorithmique, le hasard joue évidemment un grand rôle. Si l’évolution était purement algorithmique, elle serait totalement prévisible, ce qui, sauf dans des cas particuliers, paraît être une affirmation absurde. Si l’on croit que les bactéries sont des machines de Turing, faut-il admettre que les bactéries contiennent dans leurs gènes le programme pour évoluer vers l’homme ?


Ajout : Ce billet était en fait un commentaire qui a évolué, mais la conversation continue. David renvoie à un article d’Antoine Danchin sur le sujet :

http://www.pubmedcentral.nih.gov/articlerender.fcgi?tool=pubmed&pubmedid=19016882

Je n’ai pas encore eu le temps de le lire en détail, mais un aspect que je retiens est l’idée de « création d’information ». N’est-ce pas justement cela qui fait toute la différence ?

About the author

Tom Roud

Blogger scientifique zombie

21 Comments

  • Il me semble que ce qui fait la différence ce sont les lois du chaos. Si on change quelques octets aléatoirement dans le code compilé d’un programme d’ordinateur, dans le meilleur des cas ça change 3 pixels à l’affichage, mais la plupart du temps, le programme n’est plus lisible du tout. Dès qu’on sors des clous de ce qui a été intentionnellement programmé, il n’y a plus rien à tirer. On n’obtiendra que rarement un comportement imprévisible nouveau (la seule nouveauté vient du programmeur ou de l’utilisateur).

    Dans le vivant, il me semble qu’une petite variation dans le code génétique est capable d’engendrer des phénomènes complètement nouveaux, et d’ailleurs les variations aléatoires sont mises à contribution lors de la reproduction pour générer de la variété (ce qui je suppose permet de s’adapter rapidement à des changements d’environnements). En fin de compte dans le vivant, on est dans un univers chaotique ou la moindre variation peut se répercuter à grande échelle, alors que dans l’informatique, on est dans un univers où la moindre variation fait tout planter…

  • L’oracle dit : pour trouver les algorithmes permettant de passer de l’ARN à l’homme, il faudrait une machine plus grande que l’univers, avec un temps de calcul plus long que l’âge de l’univers, ce qui ne peut pas être.

  • @ quentin : c’est vrai que le vivant est beaucoup plus « résilient » qu’un ordinateur qui s’arrête dès qu’il bugge, c’est aussi une différence.
    @ all : enfin l’oracle, il est aussi peut-être là pour « créer » des structures auto-organisées, comme l’os dont parle Xochipilli à la fin de ce billet :

    http://webinet.blogspot.com/2009/08/celadon-la-clef-de-la-craquelure.html

    Il ne faut pas voir la main de Dieu partout, mais en ce sens, vous rejoignez la religion de Stuart Kaufman :
    http://tomroud.cafe-sciences.org/2008/11/13/notes-de-lecture-ii-evolution-physique-et-emergence/

  • @quentin:
    Il ne faut pas mélanger l’univers dans lequel s’exécute la simulation avec la simulation elle-même. Dans le cas d’un univers informatique, ses bugs peuvent être compensés par un système de redondances/corrections matérielles et logicielles. Dans le cas de la simulation qui s’exécute, tu peux concevoir des algorithmes type « génétiques » pour lesquels les bugs ne font que relever un peu le taux de mutation (viables ou non parmi la population en reproduction).

    @tomroud:
    L’aléatoire est un aspect du problème. Mais, avant ça, question : Il me semble qu’une machine de Turing s’applique en espace+temps discret non ?

  • « Si la vie est pure mécanique, comment expliquer le libre-arbitre ? »
    Il faut lire Spinoza…

    • Si la vie est pure mécanique, comment expliquer le libre-arbitre ?

      Schrodinger n’a peut-être pas lu Spinoza, mais sa réponse ne manque pas de sel : en gros, si j’ai mon libre-arbitre dans un monde mécanique, c’est que je suis Dieu 😛 !

      • (petit essai de réflexion « en live », ouvrant quelques questions)

        Puisque tu parles de mécanique, tu n’as pas répondu à ma question sur l’aspect espace+temps discret des machines de turing. L’ajout de « parallèle » doit être précisé. Est-ce du parallèle en nombre fini, en dénombrable non fini ou en puissance du continu ? Suivant la réponse, on ne peut pas appliquer les mêmes résultats/limitations théoriques il me semble, non ? De plus, cela ne règle pas non plus le problème du temps (intrinsèquement continu, dénombrable ou discret à toute petite échelle ?), à moins que l’on ne considère que des phénomènes dont la manipulation des relations peut se ramener à du discret ? Il en va de même des positions (intrinsèquement continue, dénombrable ou discret à toute petite échelle ?), géométries et formes de manière plus générale.

        Ainsi, si on peut tout ramener à « émergence sur relations », c.à.d indépendance du substrat » (contrairement à ce que pensent des gens comme Searle, Penrose et Eccles), il faut peut-être des architectures qui utilisent au moins le dénombrable sinon la puissance du continu* (qui serait alors une propriété nécessaire du substrat, c’est à dire que le libre arbitre serait d’une manière ou d’une autre contenu dans la notion d’infini) : espace ou temps suffit-il ou espace+temps est-il nécessaire ? Physiquement, le plus simple pour le dénombrable est de le considérer comme inclus dans le continu, donc de partir directement sur du continu si on veut utiliser de l’infini inclus dans le borné et non comme phénomène limite, et d’utiliser des architectures basées sur la propagation de phénomènes physiques : circuits analogiques plutôt que numérique pour le temps, circuits optiques/électromagnétiques ou biologiques (éviter si on veut arriver à la biologie sans biologie) ou je ne sais quoi d’autre encore pour le temps+l’espace. Le probabiliste intrinsèque du quantique est il nécessaire (ontologie à la d’espagnat par exemple) ? Ou le pseudo-hasard issu du chaos classique est-il suffit ? A moins que, un peu comme à la leibniz, on puisse jouer sur les échelles, et en l’actualisant avec les fractales, tout mettre dans les replis sans fins du borné ?

        Dans tous les cas, la réflexion de Leibniz sur liberté, contingence et détermination reste valable même si d’une part cela établit toute liberté à l’image de la liberté du tout (immanence) et que cela ne règle pas le problème de l’émergence de la conscience. On peut aussi dépasser tout ça, ainsi que ta remarque en faisant appel au multivers s’il existe (même si le problème se repose aussi en considérant le multivers lui-même).

        Par ailleurs, il semblerait que hasard et indécidabilité aient un rapport d’après le résultat de Calude d’il y a quatre ou cinq ans. Cela ne devrait pas être sans conséquences …

        *En plus, des travaux récents semblent montrer qu’il faille reconsidérer l’axiome du continu et qu’il faille considérer un infini entre celui du dénombrable et celui du continu.

        • Sur continu vs discret, ce n’est pas du tout clair ce qui se passe. Par exemple, certains gènes fonctionnent avec un très petit nombre de protéines par cellule, donc les effets discrets stochastiques jouent un grand rôle. En fait, cela signifie que selon les problèmes, la bactérie se place dans un domaine soit discret, soit continu. Sur l’espace, je dirais continu, ainsi que sur le temps.
          Note cela dit que l’analogie que les gens font avec l’informatique est discrète presque par définition, non ?

          Je pense que peu de personnes contesteraient la présence d’effets émergents en biologie (c’est un peu la thèse aussi de Stuart Kauffman), non :

          http://tomroud.cafe-sciences.org/2008/11/13/notes-de-lecture-ii-evolution-physique-et-emergence/

          Je pense également que pas mal de gens accepteraient l’idée que les circuits biologiques sont plus analogiques que digitaux même s’il y a des exemples de réponses « digitales » (j’imagine pour des événements « catastrophiques » comme la mitose par exemple). Typiquement, les circuits biologiques me semblent relativement « mous », mais je me trompe peut-être.

          Je ne crois pas du tout à ces histoires qui essaient de mettre du quantique dans la biologie, je pense que les fluctuations thermiques seules sont suffisantes pour mettre du vrai hasard. C’est aussi pour cela que j’ai bien aimé l’idée de retrouver la méca Q à partir d’un terme de mouvement brownien. Comme on a la mécanique brownienne naturellement dans les cellules, pourquoi invoquer la physique quantique ?

          Je ne connais pas le résultat de Calude, qu’est-ce ?

        • > Je ne crois pas du tout à ces histoires qui essaient de mettre du quantique dans la biologie, je pense que les fluctuations thermiques seules sont suffisantes pour mettre du vrai hasard. C’est aussi pour cela que j’ai bien aimé l’idée de retrouver la méca Q à partir d’un terme de mouvement brownien. Comme on a la mécanique brownienne naturellement dans les cellules, pourquoi invoquer la physique quantique ?

          Juste une pure spéculation : ce que peut apporter la méca Q par rapport au mouvement brownien, c’est une intrication (une corrélation des hasards), même très faible. C’est peut être ce « petit plus » qui expliquerait certaines formes d’émergence ?

  • Petit apparté du pseudo-littéraire qui est en moi:
    « Si la vie est pure mécanique, comment expliquer le libre-arbitre? »

    Pour une réflexion intéressante sur ce sujet alliée à un bon roman, je te conseille Thinks (Pensées Secrètes) de D. Lodge.
    La plupart de ses romans valent le coup d’ailleurs: c’est un ex-universitaire, donc c’est un des précurseurs des « academic novels » (Alison Lurie, et d’autres ont pris le relais): bien que ça soit injuste de réduire ses romans à ça, le contexte particulier nous parle. Et puis en tant que prof de lettres et critique littéraire, il aime bien pasticher d’autres écrivains, et il y a souvent des réflexions intéressantes dans ses romans, et un humour « so british ». Plusieurs niveaux de lecture, en somme.

  • @Judem : les simulations sont un cas très particuliers de programmes informatiques. Il est naturel qu’on y retrouve des cararctéristiques du vivant, puisqu’ils sont fait pour ça (mais leur périmètre est bien sûr limité, et puis on n’y retrouve que ce qu’on y a mis).

    Dans mon commentaire je voulais parler de l’environnement informatique en général, celui au sein duquel opère le « hacker ». On constate que dans cet environnement la quasi-totalité des programmes ne sont pas génétiques (sauf le filtre anti-spam ?) et sont conçu au contraire pour éliminer le hasard, avec notamment, comme vous le faites remarquer, les systèmes de correction d’erreurs.

    Les programmes informatiques sont donc généralement conçu dans une démarche qui est à l’exact opposé du vivant, puisque tout est fait pour éliminer la sensibilité aux conditions initiales (imaginez que votre logiciel n’ait plus rien à voir avec celui que vous avez acheté après quelques années…)

    • Les logiciels actuels sont encore rudimentaires. Des logiciels évoluant (pour s’amélioer par exemple) constitueraient déjà un progrès. Les simulations sont plus intéressantes que nombre de logiciels actuels. Peut-être les progrès viendront-ils de « jeux évoluant » lorsque les techniques de l’IA des personnages joués par l’ordi permettront l’émergence de conscience ?

      • Encore faudrait-il savoir exactement ce qu’est la conscience et la façon dont elle émerge de la matière… Je pense que c’est un petit peu présomptueux pour l’instant d’affirmer qu’elle puisse émerger d’un programme, sans même savoir ce qu’elle est (et sachant que le fonctionnement d’un programme est à l’opposé de celui du vivant). Je pensais que l’hypothèse de l’IA forte n’était plus trop d’actualité…

        Les simulations ont toujours lieu au sein d’un périmètre restreint et pré-défini. Elles sont infiniment moins complexe qu’une cellule biologique. Elle nécessitent forcément une action humaine, dans la conception ou par la suite, pour faire apparaitre des choses nouvelles et intéressantes. Leur autonomie est limitée. A mon avis ça tient toujours au fait que l’informatique est conçu pour éliminer le hasard, tandis que le vivant fait exactement l’inverse.

        A mon avis l’informatique tel qu’il est conçu aujourd’hui (c’est à dire basé sur le calcul déterministe) ne pourra jamais être qu’une extension de notre propre esprit, c’est à dire un outil, mais est incapable de faire émerger quoi que ce soit de réellement autonome. S’il devait y avoir une évolution vers une réelle autonomie de conscience, il faudrait qu’elle ait lieu au sein même des puces électroniques.

  • c’est ausant, cette réflexion sur les oracles, et ça ressemble bien au lien entre deéterminisme et darwinisme. Je m’explique.
    Effectivement, c’est assez peu connu, mais Turing avait introduit les oracles pour résoudre les problèmes sans solution à l’intérieur du système considéré.
    Par oracle, il faut entendre, solution au hasard, puisque c’est ce que faisaient les grecs, en allant faire semblant de pêcher une solution acceptable par tous auprès d’un devin.
    Donc enr éalité, les limites de la machien de Turing avaient été traitées par Turing, qui en étaitparfaitement conscient.
    L’analogie avec la bactérie que vous suggérez est donc bien vue: on peut dire, une bactérie ayant atteint un état de son code qui ne permet pas de résoudre certains problèmes, trouvera la solution par le hasard, en dehors du système ce qui crée un nouveau système. Donc en réalité, la machine qui n’est pas de Turing dans ce cas, est encore de Turing, par les oracles de Turing. C’est comique.
    Le parallèle avec Darwin, c’est l’idée que le Darwinisme soit en fait déterministe, et que ce déterminisme soit encore Darwinien. Tout le monde pense que pour Darwin les animaux sont obtenus au hasard, alors qu’en réalité, Darwin explique longuement qu’il est très facile de concevoir les animaux, par l’imagination, les uns à partir des autres, par extrapolation de l’archétype, simplement en l’étirant et l’aplatissant dans certaines directions. Donc en réalité, les modèles déterministes de morphogenèse, qui sapent la vision habituelle du Darwinisme sont encore darwinien. C’est comique aussi.

    • Oui, ce qui me frappe un peu dans la discussion est l’oubli du fait que Turing lui-même voyait ses machines comme des objets limités. C’est même pour cela qu’il les a inventées, pour définir et déterminer la classe de problèmes solubles par des algorithmes.
      Sur Darwin, je pense que le débat repose sur la génération de nouvelles formes. Le « préjugé » classique est que la génération de forme se fait au hasard, donc que les nouvelles formes trouvées sont elles-mêmes aléatoires. Or :

      – il n’est pas clair que la génération de forme soit si aléatoire, dans le sens où il y a des contraintes physiques sur l’évolution (ça c’est ce que vous diriez)

      – quand bien même le moteur serait purement aléatoire, les formes trouvées ne le sont pas nécessairement. Si un problème n’a qu’une solution, si on utilise un algorithme génétique pour le résoudre, on finira par trouver LA solution.

      Je ne connais pas tout Darwin, mais il me semble que comme vous dites Darwin propose un modèle d’évolution assez incrémental, donc la génération de forme n’est pas si aléatoire. Puis il propose un mécanisme de fixation de ces formes : la sélection naturelle, qu’on peut voir en réalité comme un algorithme simple pour trouver les formes « optimales ». Mais cela n’est rien de plus qu’un algorithme, si l’espace des formes optimales est simple (avec un minimum par exemple), le résultat de l’algorithme est effectivement déterministe.

  • Darwin écrit bien :

    If we suppose that the ancient progenitor, the archetype as it may be called, of all mammals, had its limbs constructed on the existing general pattern, for whatever purpose they served, we can at once perceive the plain signification of the homologous construction of the limbs throughout the whole class.

    donc en réalité, pour Darwin, l’imagination comprend instantanément la construction d’un animal, à partir de l’archétype (ailleurs il évoque les allongement et aplatissements nécessaires).

    Pourquoi ce serait si facile pour l’imagination, et si diffiicle pour l’évolution? C’est aussi facile pour l’évolution, que cela l’est pour l’imagination, parce que c’est toujours tout droit (transformations pratiquement affines, sauf quelques régions où ça tourne).

    Lire aussi :

    We have seen that the members of the same class, independently of their habits of life, resemble each other in the general plan of their organisation. This resemblance is often expressed by the term `unity of type;’ or by saying that the several parts and organs in the different species of the class are homologous. The whole subject is included under the general name of Morphology. This is the most interesting department of natural history, and may be said to be its very soul. What can be more curious than that the hand of a man, formed for grasping, that of a mole for digging, the leg of the horse, the paddle of the porpoise, and the wing of the bat, should all be constructed on the same pattern, and should include the same bones, in the same relative positions? Geoffroy St Hilaire has insisted strongly on the high importance of relative connexion in homologous organs: the parts may change to almost any extent in form and size, and yet they always remain connected together in the same order. We never find, for instance, the bones of the arm and forearm, or of the thigh and leg, transposed. Hence the same names can be given to the homologous bones in widely different animals. We see the same great law in the construction of the mouths of insects: what can be more different than the immensely long spiral proboscis of a sphinx-moth, the curious folded one of a bee or bug, and the great jaws of a beetle? yet all these organs, serving for such different purposes, are formed by infinitely numerous modifications of an upper lip, mandibles, and two pairs of maxillae. Analogous laws govern the construction of the mouths and limbs of crustaceans. So it is with the flowers of plants.

    Nothing can be more hopeless than to attempt to explain this similarity of pattern in members of the same class, by utility or by the doctrine of final causes

    vous avez bien lu : « independently of their habits of life ». Le plan général qu’ils suivent n’est pas touché par leurs biotopes.

  • @tomroud et quentin:

    Informatique/électronique et discret : c’est vrai pour les ordis actuels et de nombreux circuits de traitement de l’information (autres que certaines fonction d’entrée/sortie de base ou filtrage classique). Cela dit, sans aller jusqu’à la recherche sur l’ordi quantique, il y a des chercheurs qui travaillent sur des circuits de traitement analogiques haut niveau de l’information. S’il est facile de concevoir des réseaux neuronaux artificiels analogiques, ce n’est d’ailleurs pas la seule chose qu’on peut faire. Personnellement, un peu à la limite de mes recherches (en vision par odinateur, domaine où l’IA est plus que jamais d’actualité*), j’ai une collaboration sur une idée que j’ai eu pour implanter une classe non négligeable de traitements utiles dans mon domaine, non comme c’est fait classiquement de manière numérique, mais en électronique analogique, les calculs se faisant extrêmement rapidement par des phénomènes de propagation non linéaires dans des réseaux électriques (implantés sur circuits), ouvrant aussi la possibilité d’autres traitements. J’utilise donc sur ce sujet un traitement continu au niveau temporel (à l’intérieur des puces, en utilisant ce qui se passe entre les composants électroniques élementaires; ça va un peu au-delà de ce qu’on appelle des « rétines artificielles » par le nombre de traitements possibles avec le même circuit, même si des parties numériques sont nécessaires pour constituer une unité de traitement spécialisée qui soit complète). Par ailleurs, la personne avec qui je collabore a des travaux où il utilise des phénomènes de propagation électriques sur des membranes biologiques. Ce genre de recherches n’est pas forcément courant et très connu mais pas exceptionnel non plus et peut-être que cela aboutira un jour à relativiser un peu l’informatique numérique.

    *je rappelle que contrairement à ce que les chercheurs en IA pensaient il n’y a pas si longtemps que cela, il y a plus d’intelligence dans les sens que dans la logique (je n’ai plus le chiffre exact, mais il me semble bien que 70% de la puissance du cerveau humain est dédiée à « voir »).

    informatique et hasard : au contraire, la production et l’utilisation de « véritable » hasard est un challenge en informatique depuis un moment déjà (notamment pour des simulations diverses et variées).

    discret, dénombrable et continu : par dénombrable, dans cette énumération, j’entends bien entendu dénombrable non discret (car le discret est soit fini soit dénombrable sans points d’accumulation non à l’infini), c’est à dire avec points d’accumulation non à l’infini. C’est peut-être une alternative. Il y’en a peut-être d’autres (cf. ma remarque lors d’un commentaire précédent).

    continu et biologie : même si on n’est pas en petite échelle, il me semble que les interactions qui font intervenir de la « géométrie » ne peuvent qu’inclure une part de continu, non ?

    Calude et cie : cf. http://www.pourlascience.fr/ewb_pages/f/fiche-article-presque-tout-est-indecidable-18618.php , notamment sur le lien avec les probas. D’une manière générale, je recommande les articles (dans Pour La science, rubrique « logique et calcul ») et ouvrages de J.P. Delahaye (où des tas d’avancées intéressantes sont abordées sur des domaines liés à l’info et aux maths dont parfois sur l’IA, le hasard, les automates, les infinis, etc. et bien souvent aussi avec des aspects « philo des sciences » assez intéressants).

  • Quel problème résoud la vie ?

    Ce qui est indécidable, c’est un problème, typiquement trouver à coup sur si un programme informatique termine quelles que soient ses données, en info.

    Pour la notion d’oracle, je connais pas l’oracle de l’indécidabilité, mais plutôt celui du déterminisme : certains algorithmes ou machines de Turing ne sont pas déterministes, ils laissent le choix entre plusieurs instructions pour le pas suivant de l’algorithme, pour simplifier, ce qui conduit à une explosion combinatoire si on laisse le choix plusieurs fois dans un même programme, qui servent dans le problème P=NP. L’oracle est le truc qui permet de « faire le bon choix », donc ça doit marcher aussi dans le cas de problème indécidables : quand l’un de ses choix produit « oui » et l’autre choix produit « non » comme réponse au problème, l’oracle choisit … merci l’oracle.

    Sinon, si on prend un programme quelquonque, il n’est pas plus décidable que n’importe quoi, il s’exécute, point. Pour introduire des problèmes de décidabilité, il faudrait poser question sur les propriétés de ce programmes, de son but.

    Mais dans le cas d’un programme qui imiterait la vie, la question n’a pas de sens pour moi. Comme la question de la décidabilité d’une bactérie n’aurait pas de sens.

Leave a Comment