Le malentendu zombie de l’informatique théorique

Le malentendu zombie de l’informatique théorique

Introduction

• Le manuel "Introduction to the Theory of Computation" de Michael Sipser contient un exercice parfait
• Exercice : « Si la fonction f:{0,1}*→{0,1} renvoie 1 ou 0 selon que Dieu existe ou non, alors f est-elle calculable ? »
• Réponse : « Oui, f est calculable » (parce qu’une fonction constante est calculable)

Le concept de calculabilité

• La calculabilité s’applique aux fonctions ou aux suites infinies
• Elle ne s’applique pas à une question isolée à réponse oui/non, ni à un entier isolé
• La difficulté d’écrire un programme n’a rien à voir avec la calculabilité

Le problème P contre NP

• Le problème P contre NP est une question isolée à réponse oui/non
• La NP-difficulté s’applique aux fonctions ou aux langages
• Le problème P contre NP ne peut être ni non calculable ni NP-difficile

La fonction Busy Beaver

• La fonction Busy Beaver est non calculable
• Un entier isolé comme BB(6) est calculable
• C’est la fonction BB dans son ensemble qui est non calculable

Le malentendu zombie de l’informatique théorique

• Il consiste à appliquer par erreur à des entiers isolés et à des problèmes ouverts des concepts qui s’appliquent aux suites infinies et aux fonctions
• Il consiste aussi à confondre la non-calculabilité du problème de l’arrêt avec l’incomplétude de Gödel

Question aux lecteurs

• L’auteur demande aux lecteurs comment empêcher ce malentendu zombie

Résumé de GN⁺

• Cet article traite de malentendus fréquents en informatique théorique
• La calculabilité s’applique aux fonctions ou aux suites infinies, et non aux entiers isolés ni aux questions à réponse oui/non
• Le problème P contre NP est une question isolée, sans lien avec la notion de NP-difficulté
• La fonction Busy Beaver est non calculable, mais ses valeurs prises individuellement sont calculables
• Cet article aide à mieux comprendre clairement les concepts fondamentaux de l’informatique théorique

[GN⁺]

Commentaire Hacker News

• La question de l’existence d’un algorithme calculant la complexité de Kolmogorov est liée à l’infini

  • Il n’existe pas d’algorithme capable de calculer la complexité de Kolmogorov de chaînes de longueur arbitraire
  • En revanche, il existe un algorithme pour calculer la complexité de Kolmogorov des chaînes de longueur inférieure à n
  • Cela est possible en construisant une immense table de correspondance pour toutes les chaînes possibles
  • Un problème fini peut toujours être résolu par un programme, mais ce n’est pas le cas d’un problème infini

• Avis selon lequel les mathématiques constructives correspondent mieux à l’intuition des gens

  • Il n’existe toujours aucune preuve qu’un programme pour le problème P=NP existe
  • Mark Braverman a démontré que tous les ensembles de Julia (quadratiques) sont calculables, mais pas de manière uniforme
  • En mathématiques constructives, on divise le plan complexe en plusieurs régions et on prouve que l’ensemble de Julia est compact dans chacune d’elles

• Pourquoi il est difficile de comprendre l’indécidabilité du problème de l’arrêt

  • L’un des deux programmes, "return true" et "return false", donne toujours la bonne réponse
  • L’indécidabilité n’apparaît que lorsqu’on l’étend à une infinité de combinaisons machine/entrée

• Formulation de problèmes nécessitant la logique modale

  • La question « f est-elle calculable ? » est, du point de vue modal, mal posée
  • La question « f pourrait-elle être calculable ? » est plus précise
  • C’est similaire à une directive de compilateur ou à une pragma

• Formulation déroutante de la fonction f

  • La fonction f ne bifurque pas selon la valeur de « God exists »
  • Que f vaille 0 ou 1, elle est calculable
  • La confusion vient du fait de faire entrer une variable libre dans la condition de branchement

• Différences de sens entre décidabilité, calculabilité et existence

  • Le sens diffère selon qu’on se place dans un contexte académique ou quotidien
  • Les grands nombres existent et sont calculables au sens académique, mais en pratique ils ne tiennent pas dans l’univers

• Le problème des questions liées à « God exists »

  • Il n’est pas clair si « God exists » est vrai ou faux
  • C’est un problème qui survient lorsqu’on mélange langage naturel et mathématiques

• Pourquoi l’informatique théorique et la théorie de la complexité sont difficiles pour les étudiants de licence en CS

  • Des termes comme NP-hard sont remplacés par des analogies populaires et de l’imagination

• Mécontentement concernant la manière dont le blog met en évidence le texte

  • La couleur de fond du texte sélectionné ne change pas, ce qui n’est pas intuitif

• Proposition de remplacer « God exists » par une autre proposition mathématique

  • Il faut définir clairement « God exists » comme vrai ou faux