Et en particulier la deuxième loi : l'entropie d'un système isolé augmente avec le temps .

Pour ce défi,

• Un " système isolé " sera considéré comme un programme ou une fonction (abrégé en "programme" à partir de maintenant);
• Le passage du « temps » correspondra à des exécutions itératives de la sortie du programme , considéré comme un nouveau programme;
• " Entropie " sera considérée comme l'entropie de premier ordre de Shannon (à définir ci-dessous), qui est une mesure de la diversité des caractères de la chaîne.

Le défi

Votre programme doit produire une chaîne non vide qui, lorsqu'elle est exécutée en tant que programme dans le même langage, produit une chaîne avec plus d'entropie que la précédente. L'itération à l'infini de ce processus d'exécution de la sortie doit produire une séquence strictement croissante de valeurs d'entropie .

Les chaînes peuvent contenir n'importe quel caractère Unicode 9.0 . La séquence de chaînes doit être déterministe (par opposition à aléatoire).

L' entropie pour une chaîne donnée sera définie comme suit. Identifiez ses caractères uniques et leur nombre d'occurrences dans la chaîne. La fréquence p _i du i- ème caractère unique est le nombre d'occurrences de ce caractère divisé par la longueur de la chaîne. L'entropie est alors

où la somme est sur tous les caractères uniques de la chaîne. Techniquement, cela correspond à l' entropie d'une variable aléatoire discrète avec une distribution donnée par les fréquences observées dans la chaîne.

Soit H _k l'entropie de la chaîne produite par le k- ème programme, et soit H ₀ l'entropie du code du programme initial. Aussi, laissez L ₀ indiquer la longueur du programme initial en caractères. La séquence { H _k } est monotone selon les exigences du défi et est bornée (car le nombre de caractères existants est fini). Il a donc une limite, H _∞ .

Le score d'une soumission sera ( H _∞ - H ₀ ) / L ₀ :

• Le numérateur, H _∞ - H ₀ , reflète dans quelle mesure votre code "obéit" à la loi d'augmentation de l'entropie sur une période de temps infinie.
• Le dénonimateur, L ₀ , est la longueur du code initial en caractères (pas en octets).

Le code avec le score le plus élevé gagne . Les égalités seront résolues en faveur de la première soumission / modification.

Pour calculer l'entropie d'une chaîne, vous pouvez utiliser l'extrait de code JavaScript (gracieuseté de @flawr et avec les corrections de @Dennis et @ETHproductions ) à la fin de ce post.

Si l'obtention de la limite H _∞ est difficile dans votre cas particulier, vous pouvez utiliser n'importe quelle borne inférieure, disons H ₂₀ , pour calculer le score (vous utiliserez donc ( H ₂₀ - H ₀ ) / L ₀ ). Mais en tout cas, la séquence infinie d'entropies doit être strictement croissante.

Veuillez inclure une explication ou une courte preuve que la séquence d'entropies augmente, si ce n'est pas évident.

Exemple

Dans un langage fictif, considérons le code aabcab, qui lors de l'exécution produit la chaîne cdefgh, qui lors de l'exécution produit cdefghi, qui ...

Les caractères uniques du code d'origine sont a, bet c, avec les fréquences respectives 3/6, 2/6 et 1/6. Son entropie est de 1,4591. C'est H ₀ .

La chaîne cdefgha plus d'entropie que aabcab. On peut le savoir sans le calculer car pour un nombre donné de caractères l'entropie est maximisée lorsque toutes les fréquences sont égales. En effet, l'entropie H ₁ est de 2,5850.

La chaîne a de cdefghinouveau plus d'entropie que la précédente. On peut désormais sans l'informatique car l'ajout d'un caractère inexistant augmente toujours l'entropie. En effet, H ₂ est 2,8074.

Si la chaîne suivante était 42la chaîne serait invalide, car H ₃ serait 1, plus petit que 2,8074.

Si, en revanche, la séquence continuait à produire des chaînes d'entropie croissante avec une limite H _∞ = 3, le score serait (3−1,4597) / 6 = 0,2567.

Remerciements

Grâce à

• @xnor pour son aide à relever le défi, et en particulier pour m'avoir convaincu que des chaînes infinies d'entropie croissante obtenues à partir d'une exécution itérée sont en effet possibles;

• @flawr pour plusieurs suggestions, y compris la modification de la fonction de score, et pour écrire l'extrait très utile;

• @Angs pour signaler un inconvénient essentiel dans une précédente définition de la fonction de score;

• @Dennis pour une correction dans l'extrait de code JavaScript;

• @ETHproductions pour une autre correction dans l'extrait de code ;

• @PeterTaylor pour une correction dans la définition de l'entropie.

Extrait pour calculer l'entropie

function calculateEntropy() {
  var input = document.getElementById("input").value; // fetch input as string
  if (/[\uD800-\uDBFF]([^\uDC00-\uDFFF]|$)|([^\uD800-\uDBFF]|^)[\uDC00-\uDFFF]/.test(input)) {
    document.getElementById("output").innerHTML = " invalid (unmatched surrogates)";
    return;
  }
  var charArray = input.match(/[\uD800-\uDBFF][\uDC00-\uDFFF]|[^]/g);
  var frequency = {};
  for (var ind in charArray) {
    frequency[charArray[ind]] = 0;
  }
  var total = 0;
  for (var ind in charArray) {
    frequency[charArray[ind]] ++;
    total++;
  }
  var entropy = 0;
  for (var key in frequency) {
    var p = frequency[key] / total;
    entropy -= p * Math.log2(p);
  }
  document.getElementById("output").innerHTML = " " + entropy;
};

<button type="button" onClick="javascript:calculateEntropy();">calculate</button>Entropy: <span id="output">NaN</span> 
<br/>
<textarea id="input">asdf asdf</textarea>

Gelée, 0,68220949

“ȷ6ȷ5rỌ,®Ṿ€ṁṾY⁾©v⁸⁵”©v⁵

H ₉₀ = 19,779597644909596802, H ₀ = 4,088779347361360882, L ₀ = 23

J'ai utilisé des doubles longs pour calculer H ₉₀ . Les flotteurs à double précision ont indiqué à tort que H ₄₇ <H ₄₆

Le premier programme s'imprime

“…”
“ȷ6ȷ5rỌ,®Ṿ€ṁṾY⁾©v⁸⁵”©v1010

où …sert d'espace réservé pour tous les caractères Unicode avec des points de code compris entre 100 000 et 1 000 000 . La longueur réelle est de 900 031 caractères.

Le programme des secondes s'imprime

“…”
“ȷ6ȷ5rỌ,®Ṿ€ṁṾY⁾©v⁸⁵”
“…”
“ȷ6ȷ5rỌ,®Ṿ€ṁṾY⁾©v⁸⁵”©v101010

qui, à son tour, imprime

“…”
“ȷ6ȷ5rỌ,®Ṿ€ṁṾY⁾©v⁸⁵”
“…”
“ȷ6ȷ5rỌ,®Ṿ€ṁṾY⁾©v⁸⁵”
“…”
“ȷ6ȷ5rỌ,®Ṿ€ṁṾY⁾©v⁸⁵”©v10101010

etc.

Aucun de ces programmes ne fonctionne dans l'interpréteur en ligne, qui a une limite de sortie de 100 Ko . Cependant, si nous modifions le programme pour imprimer 0123456789au lieu des 900 000 caractères Unicode susmentionnés , vous pouvez l' essayer en ligne!

MATLAB, 9.6923e-005 0.005950967872272

H0 =  2.7243140535197345, Hinf = 4.670280547752703, L0 = 327

Cette nouvelle version est une version améliorée de la première "preuve de concept". Dans cette version, j'obtiens une grande augmentation de score dès la première itération. Ceci a été réalisé en "faisant exploser" la sortie du premier programme, qui est reproduit par tous les suivants. Ensuite, j'ai également essayé de trouver le minimum H0en ajoutant simplement le symbole le plus courant du code autant de fois que possible. (Cela avait évidemment une limite, car non seulement elle diminue H0mais elle augmente également L0en même temps. Vous pouvez voir l'évolution du score tracée en fonction de la taille du programme, où la taille varie en ajoutant ou en supprimant simplement 1.) les itérations sont toujours équivalentes à la version précédente ci-dessous.

a=['ns}z2e1e1116k5;6111gE16:61kGe1116k6111gE16:6ek7;:61gg3E1g6:6ek7;:61gg3E1'];11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111;;disp(['[''',a+1,'''];',0,'a=[''',a,'''];',0,[a-10,']]);'],0,[a-10,']]);']]);

La version précédente:

H0 = 4.22764479010266, Hinf = 4.243346286312808, L0 = 162

Le code suivant est inspiré du quine matlab . Il sort essentiellement à nouveau deux fois . L'indice est que pour toute itération, nous avons des nlignes de code et des n-1symboles de nouvelle ligne \n. Ainsi, à l' napproche de l'infini, le rapport des lignes de code aux sauts de ligne approche 1, et en même temps cela garantit que nous avons une croissance strictement monotone en entropie. Cela signifie également que nous pouvons facilement calculer Hinfen considérant simplement le code de génération zéro avec autant de nouvelles lignes que de lignes de code. (Que l'on peut confirmer expérimentalement, car il converge assez rapidement.)

a=['ns}z2e1kGe1116k6111gE16;:61kGe1116k6111gE16;:6ek7;:61gg3E1g6;:6ek7;:61gg3E1'];
disp(['a=[''',a,'''];',10,'a=[''',a,'''];',10,[a-10,']]);'],10,[a-10,']]);']]);