Lazi

Étude d'un postulat simplifié

Définition rapide

La fonction everything génère toutes les 1-formules de profondeur de moins de 2048 et les calcule indéfiniment en parallèle.

Comment everything est calculé

Pour que le calcul de everything ait un sens, il ne faut pas l'évaluer de manière classique (méthode paresseuse ou stricte) mais par une évaluation spéciale où toute les sous-formules subissent séquentiellement un calcul élémentaire. Pour plus de détail voir le code de everything.

Effectivité des calculs

Si vous me demandez de calculer factoriel 5 et que je vous répond 5 fois factoriel 4 vous ne considérerez pas que j'ai fourni le calcul de factoriel 5. De même si everything fournissait la formule dont le calcul représente notre univers au départ sans pour autant la calculer, alors nous ne pourrions raisonnablement pas déduire que everything est la cause de l'existence de notre univers.
Nous pouvons remarquer qu'avec l'évaluation spéciale définie toutes les 1-formules de profondeur de moins de 2048 sont effectivement calculées.

Où et quand une chose existe ?

Le postulat et sa version simplifiée n'affirme pas que tout ce qui existe est directement constitué d'une formule lazi. Il peut exister de multiples représentations entre une formule lazi et la chose représentée. Par exemple on peut imaginer que notre univers est calculé dans un système comportant des extensions de calcul particulières.
La formule everything calcule un nombre fini de 1-formules dont certaines (une proportion très faible) calculent par exemple des 2-formules (qui seront vues comme des 1-formules à l'intérieur des 1-formule). Ces calculs indirectes de 2-formules pourront être des cause d'existence.
La richesse des représentations et des modes de calcul sont infinis. On peut faire un parallèle avec notre univers : à partir de particules il peut exister une grande richesse de construction, par exemple un objet imaginé dans un esprit humain est une forme sophistiquée de représentation faite à partir de particules.
Remarquons que dans un calcul une sous-formule peut changer d'endroit, donc la place d'une chose peut varier (comme dans notre univers, ce qui n'empêche pas les choses d'exister).

Le calcul d'everything ne garde pas l'historique du calcul, et donc une chose n'existe qu'à certaines étapes du calcul d'everything. On peut comparer ce phénomène au déroulement du temps dans notre univers où l'existence des choses est temporelle.

Génération de tous les calculs possibles

Nous allons voir ici qu'indirectement everything calcule effectivement toutes les formules. everything est une formule de profondeur d'environ 800 (traduit en lazi.0.0). Comme elle calcule les formules de profondeur <2048, elle se calcule (plus exactement une version 1-formule d'everything) elle-même ainsi que des formules calculant à plus de profondeur. Simplement par augmentation de profondeur progressive on arrive à calculer toutes les formules.

Pourquoi ne pas calculer directement toutes les formules

Parce qu'il est important pour la suite que la plupart des calculs élémentaires soit dévolus au calcul des formules plutôt qu'à leur création, car ce sont les calculs qui provoquent la cohérence alors que la création est sans cohérence. Par exemple si on se contentait de juste créer toutes les formules possibles et que notre paradigme soit que tout ce qui existe se représente par une formule, alors il y aurait une probabilité quasi nulle que ce qui vous entoure continue d'obéir aux lois physiques (on verra pourquoi plus loin).

Le postulat

Tout ce qui existe a pour origine le calcul everything.

Pourquoi c'est un postulat simplifié

Parce qu'il existe bien d'autres fonction équivalente à everything et qu'il est dissymétrique d'en favoriser une.

L'exemple des entiers naturels comme micro-univers

Plutôt que de chercher notre univers, cherchons déjà une chose plus simple : l'énumération des entiers naturels sous leurs représentation binaires.
Prenons l'exemple de l'évaluation de "recurse ($F f,n → f \ n + 1) 0" qui permet de calculer tous les entiers.
Remarquons que si on utilise une évaluation paresseuse alors on ne calcule pas les entiers car l'évaluation paresseuse ne calcul que ce qui est nécessaire à l'évaluation de la formule globale, et les additions d'entier n'en font pas partie dans ce cas.

Mais everything a une manière particulière d'évaluer les formules (en évaluant récursivement toutes les sous-formules), voir le code source pour plus de détail.
Suivant la phase d'évaluation le nombre peut se trouver à différents endroits dans la formule. Mais on peut extraire à chaque étape des sous-calculs un entier naturel litéral et qui est remplacé, au bout d'un certain nombre d'étapes, par le suivant.
On voit donc que si on définit un "univers" très simple constitué d'un nombre entier et dont la loi d'évolution est l'incrémentation du nombre, alors cette univers est calculé par everything.

Multiplicité des causes

Le calcul de l'univers décrit ci-dessus se produira de multiples fois car il existe bien des manières (une infinité) d'énumérer les entiers naturels.
Comme la fonction d'énumération décrite ci-dessus est petite elle sera directement calculée par everything, elle sera aussi calculée indirectement par des fonctions générées par everything qui elles-mêmes évalurons diverses fonctions.

Nous voyons par cet exemple que la cause de l'existence de ce micro-univers (et de n'importe quel autre) n'est pas unique car il existe une infinité de réalisations du calcul. Par contre on peut trouver une cause quasiment la plus simple en "recurse ($F f,n → f \ n + 1) 0" (appelons la C1).

Le temps

everything avance par étape. Nous appelerons chaque étape un "tick" (anglicisme). Ce tick peut être vue comme une unité de temps et nous utiliserons cette analogie.

Augmentation et densité des causes

Plus le temps passe et plus le nombre de formules calculées augmente. Par exemple everything calcule un grand nombre de formules qui elles-mêmes sont proches d'everything et calculent donc elles même un ensemble de formules. Rien que ce fait provoque une augmentation de toutes les formules calculées.
Plus une formule est simple et plus la probabilité de son calcul est élevé. Cette règle est une approximation supposant qu'il n'y a pas de système de sélection des formules calculées. Nous verrons plus loins que des phénoèmes de "sélection" provoquent des disparités dans les proportions. On peut comparer ce phénomène à la sélection naturelle : les atomes s'arrengent en molécules et les molécules simples sont plus fréquentes mais la sélection naturelle engendre la vie qui provoque des disparité dans la créations de molécules complexes.

La sub-physique, les statistiques sur les causes

Revenons à notre micro-"univers" d'entiers naturels.
Imaginons maintenant que ce nombre incrémenté pense et se disent que la cause de son existence est l'existence de C1. Nous voyons qu'il a tort puisqu'il existe des formules bien plus complexes qui énumèrent les entiers.

Mais puisque nous nous occupons ici de comprendre notre univers nous ne devons pas raisonner comme un mathématicien mais plutôt comme un physicien. Les vérités mathématiques sont étayées par des preuves, et elles ne souffrent aucunne exception. Les vérités physiques sont étayées par des expériences reproductibles et qu'en pratique on s'efforce de reproduire plusieurs fois. Il s'agit donc d'un mélange de raisonnement et de statistiques : si les lois de la physique font en sorte qu'une pomme sur 1030 montent à la place de tomber nous ne pouvons pas le prendre en compte par la science physique. Un autre exemple est que le boson de Higgs est considéré comme une particule élémentaire alors qu'il existe plus d'une chance sur 10n (avec n = 8 après la découverte) que l'on en ait aucunne preuve.

Nous voyons que nous devons raisonner comme un physicien du fait que nous cherchons les lois très probables sur ce qui existe. Mais nous raisonnons sur ce qui existe en dehors de notre univers et avec d'autres méthodes et implications. Appelons cette activité scientifique la sub-physique.

Nous devons donc nous interroger sur la proportion de la cause C1 parmis les autres causes possibles. Notament si notre micro-univers en est au nombre 10100000, un hypothétique être de cet univers pourrait se demander si pour une fois le nombre suivant serait autre chose que l'incrémentation du précédant. Pour répondre à cette question il nous faut compter les causes où on a une incrémentation de 0 à 10100000 mais pas pour le nombre suivant. Une telle cause provient d'une formule plus grosse que C1 et son calcul est donc moins fréquent que celui de C1 (et des formules petites proches de C1). Nous voyons donc que parmis tous les hypothétiques être de notre micro-univers, une énorme proportion assistera au passage de 10100000 à 10100000+1, mais pas tous.

Nous venons donc de voir que la causalité physique et sub-physique n'est pas la causalité mathématique : elle est probabiliste.
En physique on fait de nombreuses expériences pour trouver la cause la plus probable, en sub-physique on a un modèle exacte (une théorie du tout) et on fait des raisonnements statistiques pour connaître les causes les plus probables.

La sélection naturelle

Nous allons élargir les critères de la sélection naturelle pour les adapters (sans les dénaturer) à la sub-physique. Pour qu'il y ait sélection naturelle il suffit que certaines choses :

  • aient plus de capacité que d'autres à engendrer des choses
  • génèrent des choses nouvelles permetant d'améliorer les capacités à engendrer des choses
  • fasse bénéficier à toute sa descendance de ses capacités

Remarquons que ces critères sont suffisants bien qu'ils soient plus larges que la sélections naturelle terrestre. Ils se
distinguent par :

  • la non nécessité de la mort : il suffit qu'il y ait prolifération par rapport à d'autres familles de choses. Le fait que la place soit infinie évite la nécessité de la disparition.
  • la non nécessité de l'héritage : elle est remplacée ici par le critère plus large "fasse bénéficier à toute sa descendance de ses capacités". Nous verrons plus loin avec everything un mécanisme vérifiant cette propriété et pourtant sans héritage (l'héritage est néamoins un mécanisme puissant).

Vitesse de calcul ou le coût de la virtualisation

Pourquoi parler de virtualisation

Quand une n-formule exécute le calcul d'une (n+1)-formule nous avons une situation similaire à un ordinateur simulant le fonctionnement d'un ordinateur comme cela se fait avec la virtualisation en informatique. Nous utiliserons ce terme à chaque fois qu'une formule est calculée par une autre, même si le système de calcul est différent, du moment qu'il est traduisible en un calcul sur une n-formule.

L'importance que d'un faible coût de virtualisation

Pour que la sélection naturelle décrite ci-dessus puisse se réaliser, il faut que le gain des innovations soient productifs. Or la création d'innovations passe par un niveau supplémentaire de représentation (c'est à dire par une virtualisation). Donc si le coût de la virtualisation est trop élevé alors les formules enfants (celles ayant un niveau supplémentaire de représentation) sont très désavantagées et cela cré une pression à produire beaucoups d'enfants (coût plus faible) plutôt qu'à calculer efficacements. On retombe alors dans le cas déjà décrit où le fait de favoriser la création au détriment des calculs provoque une grande réduction de la cohérence.

Facteur de ralentissement par interprétation

Dans cette partie technique (on pourra l'ignorer et passer directement à "Les gains d'efficacité") nous montrons que everything a un coût fort mais que la virtualisation peut avoir un coût faible puisqu'il est en O(1). Remarquons que ce résultat est déjà connu en informatique concrète où l'on a des logiciels de virtualisation qui peuvent tourner à une vitesse acceptable même sans accélération matérielle.

Interprétation suivant l'évaluation "everything"

everything avance ses formules d'un calcul élémentaire par tick (par définition). Pour les 1-formules enfants d'everything et calculant des formules de la même manière, combien faut-il de tick d'everything pour que les 1-formules enfants d'everything fasse avancer d'un calcul élémentaire les 2-formules qu'elles mêmes calculent ?
Soit na le nombre d'application comportant la formule calculée.
La formule basicRules a un temps de calcul en O(1).
La formule applyRule est récursive et dépend du nombre de "apply" (na), elle a un temps de calcul en O(na).
Le nombre de calcul élémentaires produits par oneStepFormula varie entre 1 et na.
Au final, le temps de calcul d'un calcul élémentaire est en O(na) car même quand la plupart des calculs sont possibles sur les sous-formules, l'exploration des sous-formules proches des feuilles de la formule et n'ayant pas la profondeur nécessaire pour être calculées produit un nombre de calculs élémentaires improductifs proche de na.
na est souvent un nombre exponentiel en fonction de la profondeur de la formule.

Interprétation suivant l'évaluation "paresseuse et marqueur de calcul"

Remarquons que pour que les calculs des choses soient effectifs nous ne pouvons pas utiliser une évaluation purement paresseuse basique (sans système de partage de valeur) car alors les choses ne sont éventuellement calculées que dans les conditions des "if", valeurs perdues après évaluation de la condition.

Pour arriver à une effectivité des calculs de manière relativement efficace nous pouvons ajouter des annotations aux sous-formules afin d'indiquer quelles sous-formules calculer avant de réaliser le calcul sur la formule globale. Mais pour limiter la recherche de ces annotations on peut ne les chercher que dans les arguments directes, à la manière de l'opérateur "!" d'Haskell.

Calculer en parallèle et en interprétation paresseuse en O(1)

Avant de prendre en compte les nécessaires annotations de calcul d'arguments, nous allons déjà montrer que nous pouvons calculer les formules en parallèle en évaluation paresseuse avec un temps de calcul en O(1) par rapport au nombre de calcul élémentaires réalisés sur les formules à calculer.

Si on utilise simplement une formule réalisant un seul calcul élémentaire sur une 1-formule alors on ne peut pas avoir un temps de calcul en O(1) car la sous-formule où le calcul élémentaire doit être réalisé nécessite une recherche dépendant de la profondeur de la formule .
C'est pourquoi il est nécessaire de réaliser non pas un mais une liste de calcul élémentaires sur la formule de manière à annuler l'effet de la recherche de l'endroit à calculer. On peut déterminer la longueur de la liste en fonction de la longueur de la recherche nécessaire. Et c'est donc une longueur variable en fonction des formules.
On se trouve alors, pour chaque formule à calculer, avec une liste de résultats intermédiaires correspondant à l'application des calculs élémentaires. À partir de ces listes on avance dans les calculs et on calcule une nouvelle liste quand on n'a plus de résultats en réserve.

Remarquons qu'avec l'algorithme décrit on doit pour chaque calcul élémentaire (exécuté sur une sous-formule) reconstruire la formule entière. Donc il faut ajouter les arguments et on sort alors d'un temps de calcul en O(1) car le nombre d'argument est quelconque. Pour parer à ce problème il est nécessaire d'adopter une représentation des formules où l'on peut représenter n arguments (et non un seul comme dans l'application).

Il reste donc à prouver que l'interprétation paresseuse d'une formule peut se faire en un temps O(1) (quand le calcul est infini, sinon cela n'a pas de sens).
C'est l'objet du théorème de l'évaluation lazy en O(1).

Calculer en interprétation "paresseuse et marqueurs de calcul" en O(1)

Comme on a vue que l'évaluation paresseuse est en O(1) il nous suffit de montrer que la recherche de marqueurs de calcul d'argument est en O(1). Or en lisant la démonstration du théorème de l'évaluation lazy en O(1) on voit que l'on parcourt déjà les arguments supplémentaires (pour les empiler). Cet algorithme étant O(1), ajouter un test au moment de l'empilement ne change pas la nature O(1) du calcul. Remarquons que les arguments non empilés ils sont en quantité fixe (3).

Les gains d'efficacité

Mesurer l'efficacité d'un seul calcul

On peut mesurer l'efficacité à réaliser un calcul en comparant le nombre de calculs élémentaires nécessaires pour avancer dans le calcul. Ce nombre de calcul élémentaires varie au fur et à mesure du calcul, c'est donc son évolution qui permet de mesurer l'efficacité. Par exemple si on énumère les entiers naturels, une méthode simple où l'on incrémente l'entier utilisera de plus en plus de calculs élémentaires au fur et à mesure que l'entier grandit.

Cas simple / cas complexe

Maintenant que nous avons vu qu'il existe un phénomène de sélection naturelle, il devient intéressant de chercher à voir vers où il peut mener.
Pour étudier la question, prenons un exemple simple et un complexe de choses calculées :

Comme exemple simple nous reprendrons l'énumération des entiers naturels. On peut montrer que l'on a une quantité d'opérations minimales pour réaliser ce calcul et que la fonction optimale est relativement simple. Donc le gain en efficacité pour réaliser ce calcul ne peut être très grand.
Comme exemple complexe nous prendrons l'énumération, ordonnée par taille de formule, de tous les théorèmes d'une mathématique donnée. Notre habitude de l'esprit humain nous montre qu'il existe des différences d'efficacité énormes entre les différentes méthodes pour réaliser cette énumération.

Les calculs multiplexés

On peut calculer plusieurs choses en même temps ce qui permet d'augmenter l'efficacité. Par exemple on peut énumérer les entiers naturels et aussi énumérer les entiers pairs.

Remarque : Dans le calcul sans saut la séquence 4,6,8 n'existe pas (mais 4,5,6,7,8 existe), donc on ne peut pas considérer que le calcul sans saut inclue le calcul avec saut.

Augmenter l'efficacité par multiplexage des calculs

Quand deux calculs son très proches on peut réaliser parfois les deux calculs en même temps et ainsi gagner en efficacité puisqu'on réalise alors l'équivalent de plusieurs calculs en un seul. On voit que la sélection naturelle pousse au multiplexage des calculs puisqu'il y a par la une augmentation de la productivité.

Automatiser le multiplexage par les bits quantiques

Nous avons vu que le multiplexage des calculs augmentait l'efficacité, nous allons présenter maintenant une technique générique de multiplexage.

Nous introduisons de nouvelles règles de calculs et nouvelles représentations de formules :

  • Un nouveau type de formule : la superposition d'état : cette formule représente la superposition de valeurs de formules.
  • Il est nécessaire que la règle "distribute x y z → (x z) (y z)" utilise une référence pour z de sorte qu'il n'est pas réellement dupliqué et remplacé par une référence. Ainsi l'évaluation de z se reporte partout où il est dupliqué. Remarquons que cette technique d'optimisation est utilisée dans l'interpréteur Lazi (pour éviter de dupliquer des calculs).
  • Notons 01b la superposition de 0b et 1b
  • if 01b x y retourne la superposition des formules x et y
  • Le calcul élémentaire d'une formule qui est une superposition est la superposition des calculs élémentaires des différentes formules.

Ainsi avec cette technique, que ce soit dans le code ou dans les données, nous pouvons réaliser plusieurs calculs plus ou moins différents et en parallèle.

Les bits quantiques du point de vue de l'observateur intérieur

Puisqu'il peut y avoir supperposition, un observateur intérieur peut se trouver dans plusieurs formules supperposées. Mais que se passe t-il si un test "if 01b" donne des résultats observables suivant la valeur ? "Observable suivant la valeur" signifie que l'observateur sera différent (puisqu'il aura observé) suivant qu'il constatera que le if sera comme un if 0b ou comme un if 1b. Donc la superposition absorbera l'observateur et il y aura donc du fait de ce bit quantique une superposition d'observateurs : l'un aura observer un if 0b et l'autre un if 1b.
Si l'observateur répète l'expérience il aura alors une impression (fausse) d'aléatoire dans les lois de son univers.
Remarquons qu'il ne pourra pas constater ces phénomènes aléatoires s'il se produisent à des niveaux plus profonds comme par exemple dans les formules déterminant les constantes physiques de son univers par exemple, car alors la supperposition d'états se fait directement à grande échelle et sans répétition possible.

La duplication de données ne peut être faite que par distribute, et nous avons vu qu'il sagit en fait d'une référence, c'est à dire qu'il n'y a pas réellement de duplication. Cela implique que si l'on teste un bit quantique dupliqué, l'observateur ne pourra observer qu'une valeur possible pour les données dupliquées.

La théorie quantique en physique, l'optimisation des calculs par bits quantiques

S'il y a manifestement une relation forte entre les deux, l'aspect ondulatoire en physique n'a pas de représentation par le bit quantique.

Si on regarde notre univers d'un point de vue d'une optimisation des calculs on peut constater la grande richesse des interactions, par exemple :

  • la formule everything engendre des sous-calculs qui sont indépendants, l'un ne peut amener d'améliorations à d'autres, alors que dans notre univers il y a de multiples interactions entre les choses.
  • le calcul Lazi a un mécanisme de duplication de l'information (distribute) alors que notre univers, grâce aux ondes, envoie l'information à bien plus grande échelle : il me semble que l'aspect ondulatoire est une optimisation de transmisssion d'information car si on voulait sans le concept d'onde distribuer une information dans toutes les directions on devrait alors avoir un nombre d'intrications quantiques plus grand que le nombre de particules de l'univers simplement pour envoyer une seule information.