Y en particular la segunda ley : la entropía de un sistema aislado aumenta con el tiempo .

Para este desafío,

• Se considerará que un " sistema aislado " es un programa o función (abreviado como "programa" de ahora en adelante);
• El paso del " tiempo " corresponderá a ejecuciones iteradas de la salida del programa. , consideradas como un nuevo programa;
• " Entropía " se tomará como la entropía de primer orden de Shannon (que se definirá a continuación), que es una medida de cuán diversos son los caracteres de la cadena.

El reto

Su programa debe producir una cadena no vacía que cuando se ejecuta como un programa en el mismo idioma produce una cadena con más entropía que la anterior. La iteración infinita de este proceso de ejecución de salida debe producir una secuencia estrictamente creciente de valores de entropía .

Las cadenas pueden contener cualquier carácter Unicode 9.0 . La secuencia de cadenas debe ser determinista (en lugar de aleatoria).

La entropía para una cadena dada se definirá de la siguiente manera. Identifique sus caracteres únicos y su número de ocurrencias en la cadena. La frecuencia p _i del i -ésimo carácter único es el número de apariciones de ese carácter dividido por la longitud de la cadena. La entropía es entonces

donde la suma está sobre todos los caracteres únicos de la cadena. Técnicamente, esto corresponde a la entropía de una variable aleatoria discreta con distribución dada por las frecuencias observadas en la cadena.

Deje que H _k denote la entropía de la cadena producida por el programa k -th, y deje que H ₀ denote la entropía del código del programa inicial. Además, deje que L ₀ denote la longitud del programa inicial en caracteres. La secuencia { H _k } es monótona según los requisitos de desafío y está limitada (porque el número de caracteres existentes es finito). Por lo tanto tiene un límite, H _∞ .

La puntuación de una presentación será ( H _∞ - H ₀ ) / L ₀ :

• El numerador, H _∞ - H ₀ , refleja hasta qué punto su código "obedece" la ley de aumentar la entropía en un lapso de tiempo infinito.
• El denonimador, L ₀ , es la longitud del código inicial en caracteres (no en bytes).

El código con la puntuación más alta gana . Los empates se resolverán a favor de la presentación / edición más temprana.

Para calcular la entropía de una cadena, puede usar el fragmento de JavaScript (cortesía de @flawr y con correcciones de @Dennis y @ETHproductions ) al final de esta publicación.

Si obtener el límite H _∞ es difícil en su caso específico, puede usar cualquier límite inferior, digamos H ₂₀ , para calcular el puntaje (entonces usaría ( H ₂₀ - H ₀ ) / L ₀ ). Pero, en cualquier caso, la secuencia infinita de entropías debe aumentar estrictamente.

Incluya una explicación o una prueba breve de que la secuencia de entropías está aumentando, si eso no es evidente.

Ejemplo

En un lenguaje ficticio, considere el código aabcab, que cuando se ejecuta produce la cadena cdefgh, que cuando se ejecuta produce cdefghi, que ...

Los caracteres únicos del código original son a, by c, con las frecuencias respectivas 3/6, 2/6 y 1/6. Su entropía es 1.4591. Esto es H ₀ .

La cadena cdefghtiene más entropía que aabcab. Podemos saber esto sin calcularlo porque para un número dado de caracteres la entropía se maximiza cuando todas las frecuencias son iguales. De hecho, la entropía H ₁ es 2.5850.

La cadena cdefghinuevamente tiene más entropía que la anterior. Ahora podemos hacerlo sin computar porque agregar un carácter no existente siempre aumenta la entropía. De hecho, H ₂ es 2.8074.

Si la siguiente cadena fuera 42la cadena sería inválida, porque H ₃ sería 1, menor que 2.8074.

Si, por otro lado, la secuencia continuaba produciendo cadenas de entropía creciente con límite H _∞ = 3, la puntuación sería (3−1.4597) / 6 = 0.2567.

Expresiones de gratitud

Gracias a

• @xnor por su ayuda para mejorar el desafío y, en particular, por convencerme de que son posibles infinitas cadenas de entropía creciente obtenidas de la ejecución iterada;

• @flawr para varias sugerencias, incluida la modificación de la función de puntuación y para escribir el fragmento muy útil;

• @Angs para señalar un inconveniente esencial en una definición previa de la función de puntuación;

• @Dennis para una corrección en el fragmento de JavaScript;

• @ETHproductions para otra corrección en el fragmento;

• @PeterTaylor para una corrección en la definición de entropía.

Fragmento para calcular la entropía

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

Usé dobles largos para calcular H ₉₀ . Los flotadores de precisión doble informaron incorrectamente que H ₄₇ <H ₄₆

El primer programa imprime

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

donde …sirve como marcador de posición para todos los caracteres Unicode con puntos de código entre 100,000 y 1,000,000 . La longitud real es de 900,031 caracteres.

El programa de segundos imprime

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

que, a su vez, imprime

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

etc.

Ninguno de estos programas funciona en el intérprete en línea, que tiene un límite de salida de 100 KB . Sin embargo, si modificamos el programa para imprimir en 0123456789lugar de los 900,000 caracteres Unicode mencionados anteriormente , ¡puede probarlo en línea!

MATLAB, 9.6923e-005 0.005950967872272

H0 =  2.7243140535197345, Hinf = 4.670280547752703, L0 = 327

Esta nueva versión es una versión mejorada de la primera "prueba de concepto". En esta versión obtengo un gran aumento de puntaje desde la primera iteración. Esto se logró "explotando" la salida del primer programa, que se replica en todos los siguientes. Luego también intenté encontrar el mínimo H0simplemente agregando el símbolo más común del código tantas veces como sea posible. (Obviamente, esto tenía un límite, ya que no solo disminuye H0sino que también aumenta L0al mismo tiempo. Puede ver el desarrollo de la puntuación trazada en función del tamaño del programa donde el tamaño varía simplemente agregando o quitando 1). Las iteraciones siguen siendo equivalentes a la versión anterior a continuación.

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

Versión previa:

H0 = 4.22764479010266, Hinf = 4.243346286312808, L0 = 162

El siguiente código está inspirado en el matlab quine . Básicamente, solo vuelve a salir solo dos veces . La pista es que para cualquier iteración tenemos nlíneas de código y n-1símbolos de nueva línea \n. Entonces, a medida que se nacerca al infinito, la relación de líneas de código a líneas nuevas se acerca a 1, y al mismo tiempo esto garantiza que tenemos un crecimiento estrictamente monótono en la entropía. Eso también significa que podemos calcular fácilmente Hinfsimplemente considerando el código de generación cero con tantas líneas nuevas como líneas de código. (Cuál puede confirmar experimentalmente, ya que converge bastante rápido).

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