Bonjour, j'ai regardé cette vidéo (et d’autres) sur la probabilité a priori d’une théorie: Https://youtu.be/oBNNKf_zoq8?si=Fai4Qk6UTIVTB85A
Je me pose ces 5 questions:
Q1 Mais je ne comprend pas pourquoi la probabilité a priori serait inversement proportionnel a 2n pour une complexité de n, alors que la somme des probabilités a priori des théories de complexité n est proportionnelle à 1, car il y a 2n théories (algorithmes) différentes pour une complexité de n… Quelqu'un pour m'expliquer ?
Q2 Il y a des théories bijectives (qui donne toujours le même résultat, a+b et b+a par exemple)
Ça devrait influencer la probabilité a priori non ?
(puisqu’il y a moins de 2n théories non-bijectives différentes)
Q3 Et comment sont prises en compte les théories qui n'ont pas de sens ? (algorithmes qui renvoient des erreurs)
Q4 Pourquoi n’y a t'il pas une infinité de théories vraies ? Par exemple, une théorie pour déterminer la n-ième décimale d’un nombre irrationnel (ou univers ?), sachant qu’il y a une infinité de tels nombres, il y aurait alors une infinité de théories vraies…
Q5 Peut-être qu’on peut penser le langage pour l'adapter à chaque théorie en cherchant le meilleur langage pour la théorie.
Meilleur signifie qui permet la complexité minimum possible pour la théorie.
Ne peut-on pas calculer la version les plus simple d'un algorithme donné, avec le meilleur langage ? (pas forcément le plus rapide, simple≈”court en calcul/description” en attribuant à une boucle la valeur≈la complexité de l'initialisation, une incrémentation et une comparaison)
(en incluant les calculs pour la comparaison, par exemple n²<10 doit compter le carré, ce qui est presque équivalent a prendre a<10 en prenant a=n² a chaque fin de boucle, presque car il y a une affectation en plus. ici, n²<10 ⇔ n<10² en “complexité”)
(La multiplication étant une boucle d'addition, elle aurait une complexité constante supplémentaire à l'addition.
Une liste d'affectations ou de variables peut aussi être une boucle ? Non, sinon il faut écrire la boucle pour simplifier).
Ce n’est pas exactement simple=“court en calcul” car le simple que je décris ne dépend pas du temps d'exécution. Ce n’est pas non plus simple=”court en description” car une multiplication “” est plus complexe qu’une addition “+”.
Comment déterminer la complexité de la récursivité ?
La récursivité demande d’intégrer des “if” pour arrêter la boucle, la complexité supplémentaire est donc déjà prise en compte ?
+1 affectation pour l'appel
+1 affectation pour chaque terme de la fonction récursive.
+calcul, si calcul dans l'appel
Plutôt simple≈”court en calcul en ne prenant en compte que “le deuxième tour de boucle” en faisant comme si il y avait un deuxième tour même si il n’y en a pas. (le premier tour ne faisant pas d’itération dans les boucles, mais l’itération doit être prise en compte tout comme l’affectation…). Mais il pourrait y avoir un if else… il faut prendre toutes les possibilités en compte. Chaque calcul présent dans l'algorithme doit compter une fois.
“complexité en calcul descriptif” me paraît être une bonne manière de nommer cela.
Q6 Peut-être qu'il y a un pourcentage fixé de théories qui renvoient des erreurs indépendamment de la complexité ? Peut-on faire une estimation ?