E, em particular, a segunda lei : a entropia de um sistema isolado aumenta com o tempo .

Para este desafio,

• Um " sistema isolado " será considerado um programa ou função (abreviado como "programa" a partir de agora);
• A passagem do " tempo " corresponderá às execuções iteradas da saída do programa , consideradas como um novo programa;
• " Entropia " será tomada como entropia de primeira ordem de Shannon (a ser definida abaixo), que é uma medida da diversidade dos caracteres da string.

O desafio

Seu programa deve produzir uma string não vazia que, quando executada como um programa no mesmo idioma, produz uma string com mais entropia que a anterior. A iteração infinita desse processo de execução-saída deve produzir uma sequência estritamente crescente de valores de entropia .

As cadeias podem conter qualquer caractere Unicode 9.0 . A sequência de strings deve ser determinística (em oposição a aleatória).

A entropia para uma determinada sequência será definida da seguinte maneira. Identifique seus caracteres exclusivos e seu número de ocorrências na sequência. A frequência p _i do i- ésimo caractere exclusivo é o número de ocorrências desse caractere dividido pelo comprimento da string. A entropia é então

onde a soma está sobre todos os caracteres exclusivos da string. Tecnicamente, isso corresponde à entropia de uma variável aleatória discreta com distribuição dada pelas frequências observadas na string.

Deixe H _k denotar a entropia da string produzida pelo k- ésimo programa e H ₀ denote a entropia do código do programa inicial. Além disso, deixe L ₀ denotar o comprimento do programa inicial em caracteres. A sequência { H _k } é monótona conforme os requisitos de desafio e é limitada (porque o número de caracteres existentes é finito). Portanto, ele tem um limite, H _∞ .

A pontuação de uma submissão será ( H _∞ - H ₀ ) / L ₀ :

• O numerador, H _∞ - H ₀ , reflete em que medida seu código "obedece" à lei do aumento da entropia ao longo de um período de tempo infinito.
• O denonimator, L ₀ , é o comprimento do código inicial em caracteres (não em bytes).

O código com a pontuação mais alta vence . Os laços serão resolvidos em favor da submissão / edição mais antiga.

Para calcular a entropia de uma string, você pode usar o JavaScript trecho (cortesia de @flawr e com correções de @ Dennis e @ETHproductions ) no final deste post.

Se a obtenção do limite H _∞ for difícil no seu caso específico, você poderá usar qualquer limite inferior, digamos H ₂₀ , para calcular a pontuação (portanto, você usaria ( H ₂₀ - H ₀ ) / L ₀ ). Mas, em qualquer caso, a sequência infinita de entropias deve aumentar estritamente.

Inclua uma explicação ou prova curta de que a sequência de entropias está aumentando, se isso não for evidente.

Exemplo

Em uma linguagem fictícia, considere o código aabcabque, quando executado, produz a string cdefgh, que, quando executado cdefghi, que ...

Os caracteres únicos do código original são a, be c, com as respectivas frequências de 3/6, 2/6 e 1/6. Sua entropia é 1.4591. Este é H ₀ .

A cadeia cdefghtem mais entropia que aabcab. Podemos saber isso sem calculá-lo porque, para um determinado número de caracteres, a entropia é maximizada quando todas as frequências são iguais. Com efeito, a entropia H ₁ é 2,5850.

A string cdefghinovamente tem mais entropia que a anterior. Podemos agora sem computação, porque adicionar um caractere inexistente sempre aumenta a entropia. Com efeito, H ₂ é 2,8074.

Se a próxima string fosse 42a cadeia seria inválida, porque H ₃ seria 1, menor que 2,8074.

Se, por outro lado, a sequência continuasse produzindo seqüências de entropia crescente com o limite H _∞ = 3, a pontuação seria (3−1.4597) / 6 = 0,2567.

Agradecimentos

Graças a

• @xnor por sua ajuda para melhorar o desafio e, em particular, por me convencer de que são infinitas cadeias infinitas de crescente entropia obtidas com a execução iterada;

• @flawr para várias sugestões, incluindo a modificação da função score e para escrever o snippet muito útil;

• @Angs por apontar uma desvantagem essencial em uma definição anterior da função score;

• @Dennis para uma correção no snippet JavaScript;

• @ETHproductions para outra correção no snippet;

• @ PeterTaylor para uma correção na definição de entropia.

Snippet para calcular a entropia

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>

Gelatina, 0,68220949

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

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

Usei duplas longas para calcular o H ₉₀ . Flutuadores de precisão dupla relataram incorretamente que H ₄₇ <H ₄₆

O primeiro programa imprime

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

onde …serve como um espaço reservado para todos os caracteres Unicode com pontos de código entre 100.000 e 1.000.000 . O comprimento real é 900.031 caracteres.

O programa de segundos é impresso

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

que, por sua vez, imprime

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

etc.

Nenhum desses programas funciona no intérprete online, que possui um limite de saída de 100 KB . No entanto, se modificarmos o programa para imprimir, em 0123456789vez dos 900.000 caracteres Unicode mencionados acima , você poderá experimentar online!

MATLAB, 9.6923e-005 0.005950967872272

H0 =  2.7243140535197345, Hinf = 4.670280547752703, L0 = 327

Esta nova versão é uma versão aprimorada da primeira "prova de conceito". Nesta versão, recebo um grande aumento de pontuação desde a primeira iteração. Isso foi conseguido "explodindo" a saída do primeiro programa, replicada por todos os programas subseqüentes. Depois, tentei também encontrar o mínimo H0, acrescentando o símbolo mais comum do código quantas vezes possível. (Obviamente, isso tinha um limite, pois não apenas diminui, H0mas também aumenta L0ao mesmo tempo. Você pode ver o desenvolvimento da pontuação plotada em relação ao tamanho do programa em que o tamanho é variado apenas adicionando ou removendo 1.) as iterações ainda são equivalentes à versão anterior abaixo.

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

Versão anterior:

H0 = 4.22764479010266, Hinf = 4.243346286312808, L0 = 162

O código a seguir é inspirado no matlab quine . Basicamente, gera apenas a si próprio novamente duas vezes . A pista é que, para qualquer iteração, temos nlinhas de código e n-1símbolos de nova linha \n. Assim, como nabordagens ao infinito, a proporção de linhas de código e novas linhas se aproxima de 1, e ao mesmo tempo isso garante que tenhamos um crescimento estritamente monótono na entropia. Isso também significa que podemos calcular facilmente Hinfconsiderando o código de zero-geração com igualmente muitas novas linhas como linhas de código. (Qual deles pode confirmar experimentalmente, pois converge rapidamente).

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