On this site we obey the laws of thermodynamics!

Question

And in particular the second law: the entropy of an isolated system increases over time.

For this challenge,

• An "isolated system" will be taken to be a program or function (abbreviated as "program" from now on);
• The passing of "time" will correspond to iterated executions of the program's output, considered as a new program;
• "Entropy" will be taken as Shannon's first-order entropy (to be defined below), which is a measure of how diverse the characters of the string are.

The challenge

Your program should produce a non-empty string that when executed as a program in the same language produces a string with more entropy than the previous one. Infinitely iterating this execute-the-output process must produce a strictly increasing sequence of entropy values.

The strings can contain any Unicode 9.0 characters. The sequence of strings must be deterministic (as opposed to random).

The entropy for a given string will be defined as follows. Identify its unique characters and their number of occurrences in the string. The frequency p_i of the i-th unique character is the number of occurrences of that character divided by the length of the string. The entropy is then

where the sum is over all unique characters of the string. Technically, this corresponds to the entropy of a discrete random variable with distribution given by the frequencies observed in the string.

Let H_k denote the entropy of the string produced by the k-th program, and let H₀ denote the entropy of the initial program's code. Also, let L₀ denote the length of the initial program in characters. The sequence {H_k} is monotone as per the challenge requirements, and is bounded (because the number of existing characters is finite). Therefore it has a limit, H_∞.

The score of a submission will be (H_∞−H₀)/L₀:

• The numerator, H_∞−H₀, reflects to what extent your code "obeys" the law of increasing entropy over an infinite time span.
• The denonimator, L₀, is the length of the initial code in characters (not in bytes).

The code with the highest score wins. Ties will be resolved in favour of the earliest submission/edit.

To compute the entropy of a string, you can use the JavaScript snippet (courtesy of @flawr and with corrections by @Dennis and @ETHproductions) at the end of this post.

If obtaining the limit H_∞ is difficult in your specific case, you can use any lower bound, say H₂₀, to compute the score (so you would use (H₂₀−H₀)/L₀). But in any case, the infinite sequence of entropies must be strictly increasing.

Please include an explanation or short proof that the sequence of entropies is increasing, if that's not evident.

Example

In a fictional language, consider the code aabcab, which when run produces the string cdefgh, which when run produces cdefghi, which ...

The unique characters of the original code are a, b and c, with respective frequencies 3/6, 2/6 and 1/6. Its entropy is 1.4591. This is H₀.

The string cdefgh has more entropy than aabcab. We can know this without computing it because for a given number of characters the entropy is maximized when all the frequencies are equal. Indeed, the entropy H₁ is 2.5850.

The string cdefghi again has more entropy than the previous one. We can now without computing because adding a non-existing character always increases the entropy. Indeed, H₂ is 2.8074.

If the next string were 42 the chain would be invalid, because H₃ would be 1, smaller than 2.8074.

If, on the other hand, the sequence went on producing strings of increasing entropy with limit H_∞ = 3, the score would be (3−1.4597)/6 = 0.2567.

Acknowledgments

Thanks to

• @xnor for his help improving the challenge, and in particular for convincing me that infinite chains of increasing entropy obtained from iterated execution are indeed possible;

• @flawr for several suggestions, including modifying the score function, and for writing the very useful snippet;

• @Angs for pointing out an essential drawback in a previous definition of the score function;

• @Dennis for a correction in the JavaScript snippet;

• @ETHproductions for another correction in the snippet;

• @PeterTaylor for a correction in the definition of entropy.

Snippet for calculating the entropy

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>

Answer 1

Jelly, 0.68220949

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

H₉₀ = 19.779597644909596802, H₀ = 4.088779347361360882, L₀ = 23

I used long doubles to compute H₉₀. Double precision floats incorrectly reported that H₄₇ < H₄₆

The first program prints

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

where … serves as a placeholder for all Unicode characters with code points between 100,000 and 1,000,000. The actual length is 900,031 characters.

The seconds program prints

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

which, in turn, prints

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

etc.

None of these programs works in the online interpreter, which has a 100 KB output limit. However, if we modify the program to print 0123456789 instead of the aforementioned 900,000 Unicode characters, you can Try it online!

Answer 2

MATLAB, 9.6923e-005 0.005950967872272

H0 =  2.7243140535197345, Hinf = 4.670280547752703, L0 = 327

This new version is an improved version of the first "proof of concept". In this version I get a great score increase from the first iteration. This was achieved by "blowing up" the output of the first program, that is replicated by all the subsequent ones. Then I also tried to find the minimal H0 by just appending the most common symbol of the code as many times as possible. (This had obviously a limit, since it does not only decrease H0 but also increases L0 at the same time. You can see the development of the score plotted against the size of the program where the size is varied by just adding or removing 1.) The subsequent iterations still are equivalent to the previous version below.

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

Previous version:

H0 = 4.22764479010266, Hinf = 4.243346286312808, L0 = 162

The following code is inspired by the matlab quine. It basically outputs just itself again twice. The clue is that for any iteration we have n lines of code and n-1 newline symbols \n. So as n approaches to infinity, the ratio of lines of code to newlines approaches 1, and at the same time this guarantees that we have a strictly monotonous growth in entropy. That also means we can easily calculate Hinf by just considering the zero-th generation code with equally many newlines as lines of code. (Which one can experimentally confirm, as it converges quite quickly.)

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