Comments on Une tentative pour vulgariser les bases de la calculabilité

@ jeanas : merci pour ta proposition d’échange ; j’essaie de te solliciter sans doute dimanche le temps de gérer deux trois trucs et de voir comment je peux éventuellement créer un compte sur le rival de Twitter (j’espère juste qu’on n’est pas obligé de donner son numéro de tel pour d’authentifier). C’est sûr que ce n’est pas en rapport pertinent avec l’accès au code source.. Il était un peu question des limites éventuelles de la calculabilité tout de même et comme cette histoire d’essai de réflexivité algorithmique induite avec chatgpt m’a beaucoup intéressé (et occupé) depuis deux/trois mois allait en ce sens pour moi, je n’ai pu résister à l’idée d’envoyer la remarque. Je suis très curieux de voir si les idées que j’ai eues récemment sur les limites de principe de l’algorithmique pour simuler la pensée humaine peuvent (un peu) ou non résister à ton scepticisme !

Je n'étais pas franchement convaincu par l'argument de Dyonisos non plus.
Ceci étant, si vous discutez de cela, pourriez-vous m'inclure aussi ? (@lipsum.dev sur bsky, @lipsumdev sur Mastodon ou par email, cf lien "à propos" en bas de mon blog)

@Dyonisos : Je ne vais pas m'étendre là-dessus ici parce que ce serait hors-sujet sur ce billet, mais je serais ravi d'en discuter sur Mastodon ou Bluesky ou par mail (contacts sur la page Web en cliquant sur mon pseudo). Disons simplement que je suis très sceptique sur l'idée qu'il existerait une différence fondamentale de nature entre l'intelligence humaine et l'intelligence artificielle potentiellement réalisable, et extrêmement sceptique sur la pertinence d'appliquer des arguments inspirés de la calculabilité dans le genre de « essayons d'analyser ce qu'un programme peut faire sur son propre code source » pour comprendre ces questions.

Quand tu dis que ça ne change rien aux capacités du programme de lui donner accès à son propre code source, si on décale et qu'on essaie de lui donner accès à certaines de ses limitations inscrites en lui mais qu'il ne "réalise" pas vraiment en les lui donnant à voir sur une session où il a tourné, et qu'en même temps il est tel qu'il doit chercher dans chaque session à adapter sa réponse au mieux par rapport aux données fournies dans chaque session, est-ce qu'on ne peut pas dire :
1) le programme ne change pas dans sa structure profonde.
2) ses capacités adaptatives s'affinent dans la session où il voit ses/ces limitations, au moins au sens où il est capable de faire tourner ses calculs pour voir qu'il ne peut franchir certaines limites indépassables pour lui ?
Avec Chatgpt je me suis beaucoup amusé ces derniers temps à essayer ce faire ce genre de choses et ma conclusion est qu'on peut avoir ce genre d'impressions. Surtout, j'en ai retiré l'idée qu'il y avait un obstacle très puissant à ce qu'une IA puisse simuler tous les aspects de la pensée humaine. Je ne vois pas comment un fonctionnement algorithmique, sans s'abolir et rentrer dans des boucles de feedback indéfinies et stériles, pourrait réfléchir sur ses règles constitutives et les remettre en question, même s'il avait une mémoire et une capacité d'apprentissage à partir du moment où on n'est pas dans un cadre avec des règles intangibles comme aux échecs avec AlphaZero. Au mieux une IA dotée de capacités adaptatives aux inputs qu'elle reçoit peut simuler une réflexivité en retournant celle que lui injecte son utilisateur qui réfléchit sur elle, mais ses règles de base restent l'alpha et l'omega d'un horizon qu'elle ne peut dépasser. De manière surprenante pour moi, c'est cette idée qui m'a finalement fait penser que l'écart le plus abyssal entre la pensée humaine et l'IA n'était peut-être pas dans les réponses les plus spontanées et courantes (les qualias, la subjectivité en général, voire l'intuition par contraste avec la logique) mais dans cette capacité à réfléchir sur les règles qu'on applique et à les remettre en cause.

"Il est difficile de donner une frontière théorique nette entre les algorithmes classiques et ceux « data-driven » comme les réseaux de neurones."
Ben l'algo data-driven n'est il pas simplement la donnée de l'algo d'apprentisage, de l'algo de restitution et du data-set de training? Tous comme certains algo "classiques" n'ont de sens que si on donne la valeur de certaines constantes qu'ils utilisent.

"Il est difficile de donner une frontière théorique nette entre les algorithmes classiques et ceux « data-driven » comme les réseaux de neurones."
En pratique ce n'est pas évident. Les data-sets sont tellement énormes qu'il n'est pas évident d'aller voir ce qu'il y a dedans. Par contre, on peut tester le comportement du réseaux sur le dataset qui nous intéresse.

Bien sûr, je mets le curseur totalement d'un coté pour que l'explication reste simple.

@fakbill

Il est difficile de donner une frontière théorique nette entre les algorithmes classiques et ceux « data-driven » comme les réseaux de neurones.

Ceci étant, cette distinction me paraît importante à faire auprès du grand public pour que les gens comprennent notamment qu'il est impossible de fournir des garanties fortes sur le comportement de certains programmes.

Par ailleurs (en élargissant la question), certaines entreprise comme Meta mettent beaucoup en avant le caractère « open source » de leurs modèles en le présentant comme un gage de transparence.

On pourrait arguer que c'est un gage de transparence pour des algorithmes classiques (« code-driven », par opposition à « data-driven »), mais que dans ce cas la transparence serait de publier le jeu de données et le processus complet d'apprentissage, pas uniquement les poids qui en résultent.

"Dans ce sens, ChatGPT n'est pas un algorithme (même s'il y a des algorithmes utilisés pour, par exemple, calculer ses paramètres à partir d'un corpus d'entraînement, ou pour produire la sortie à partir de ses poids), parce qu'on ne peut pas dire qu'il réponde à une quelconque spécification."

ChatGPT prend un corpus en entrée (qu'on peut définir simplement si on prend "le corpus à telle date et pas d'update ensuite"). Sur ce corpus, il déroule une optimisation parfaitement spécifiée sur une structure de données parfaitement spécifiée. En ce sens c'est un algo.
Que tout ça soit trop gros pour que ça ait un sens de spécifier ce que le résultat de cette optimisation doit retourner pour toutes les entrées possible est une chose, mais la phase d'apprentissage est un algo (peut être avec un poil de sel/random là dedans).

@Thierry : je ne suis pas sûr d'être d'accord *mais* il est tout à fait possible que j'ai mal compris quelque chose.

Généralement, le problème de l'arrêt est présenté de la façon suivante :

Il n'existe pas de programme calculant une fonction booléenne H(m, n) telle que H(m, n) = 1 ssi le programme défini par m termine lorsqu'on lui donne en entrée n.

Les auteurs démontrent à la place :

Il n'existe pas de programme calculant une fonction booléenne H'(n) telle que H'(n) = 1 ssi le programme défini par n termine lorsqu'on lui donne en entrée n.

Cette seconde version implique la première (prendre pour H' la fonction n -> H(n, n)).

Je trouve que la présentation des auteurs a l'avantage de donner directement un ensemble d'entiers (et pas de paires d'entiers), ce qui évite de discuter du code de ces paires par exemple et permet directement d'en venir au point clef de la section 7, qui est l'existence d'un ensemble calculatoirement énumérable mais non calculable.

Du coup, j'ai l'impression qu'on peut se passer du théorème de Kleene et je trouve cela plus clair ainsi.

J'ai dit une bêtise ?

@Thomas : dans le livre de Benoît Monin et Ludovic Patey, la démonstration du fait que le problème de l'arrêt n'est pas décidable (théorème 7.8) n'utilise pas le théorème de Kleene… car c'est la définition elle-même du problème de l'arrêt (définition 7.7) qui l'utilise implicitement : le problème de l'arrêt y est défini comme l'ensemble des machines qui terminent en prenant en entrée leur propre code, ce qu'on peut effectivement faire sans perte de généralité justement grâce au théorème de Kleene.

Je me demande si le théorème de récursion de Kleene est vraiment à sa place dans une tentative de vulgarisation. En tout cas, je trouve que ce passage est assez difficile à saisir.

D'ailleurs, j'ai vu qu'un bouquin sur la calculabilité en français était sorti récemment (<URL: https://ludovicpatey.com/courses/comp-thy-2023/cr11-fr.pdf>) et, bien que le problème de l'arrêt vienne après le théorème de Kleene, ils en donnent une preuve indépendante.