W szczególności drugie prawo : entropia izolowanego systemu z czasem wzrasta .

Do tego wyzwania

• „ System izolowany ” będzie traktowany jako program lub funkcja (odtąd zwany „programem”);
• Upływ czasu będzie odpowiadał iterowanemu wykonaniu danych wyjściowych programu , uważanych za nowy program;
• „ Entropia ” będzie traktowana jako entropia pierwszego rzędu Shannona (do zdefiniowania poniżej), która jest miarą tego, jak różnorodne są znaki ciągu.

Wyzwanie

Twój program powinien wygenerować niepusty łańcuch, który po uruchomieniu jako program w tym samym języku tworzy łańcuch o większej entropii niż poprzedni. Nieskończenie iteracyjne wykonywanie tego procesu typu „wyprowadź-wyprowadzenie” musi generować ściśle rosnącą sekwencję wartości entropii .

Ciągi mogą zawierać dowolne znaki Unicode 9.0 . Sekwencja ciągów musi być deterministyczna (w przeciwieństwie do losowej).

Entropia dla danego ciągu znaków zostanie zdefiniowany następująco. Zidentyfikuj jego unikalne znaki i liczbę wystąpień w ciągu. Częstotliwość p _I o í -ty wyjątkowy charakter jest liczba wystąpień tego znaku podzieloną przez długość łańcucha. Entropia jest wtedy

gdzie suma obejmuje wszystkie unikalne znaki ciągu. Technicznie odpowiada to entropii dyskretnej zmiennej losowej z rozkładem podanym przez częstotliwości obserwowane w ciągu.

Niech H _k oznacza entropię ciągu utworzonego przez k -ty program, a H ₀ oznacza entropię kodu programu początkowego. Niech L ₀ oznacza długość początkowego programu w znakach. Sekwencja { H _k } jest monotoniczna zgodnie z wymaganiami wyzwania i jest ograniczona (ponieważ liczba istniejących znaków jest skończona). Dlatego ma granicę H _∞ .

Wynik z złożenia będzie miał wartość ( H _∞ - H ₀ ) / l ₀ :

• Licznik, H _∞ - H ₀ , odzwierciedla stopień, w jakim twój kod „przestrzega” prawa zwiększania entropii w nieskończonym przedziale czasu.
• Mianownik, L ₀ , jest długością początkowego kodu w znakach (nie w bajtach).

Wygrywa kod z najwyższym wynikiem . Więzy zostaną rozstrzygnięte na korzyść najwcześniejszego przesłania / edycji.

Aby obliczyć entropię ciągu, możesz użyć fragmentu kodu JavaScript (dzięki uprzejmości @flawr oraz z poprawkami @Dennis i @ETHproductions ) na końcu tego postu.

Jeśli uzyskanie limitu H _∞ jest trudne w twoim konkretnym przypadku, możesz użyć dowolnej dolnej granicy, powiedzmy H ₂₀ , aby obliczyć wynik (więc użyłbyś ( H ₂₀ - H ₀ ) / L ₀ ). Ale w każdym razie nieskończona sekwencja entropii musi się ściśle zwiększać.

Dołącz wyjaśnienie lub krótki dowód, że sekwencja entropii rośnie, jeśli nie jest to oczywiste.

Przykład

W fikcyjnym języku rozważ kod aabcab, który po uruchomieniu tworzy ciąg znaków cdefgh, który po uruchomieniu tworzy cdefghi, który ...

Unikalne postacie oryginalnego kodu są a, bi c, z odpowiednimi częstotliwościami 3/6, 2/6 i 1/6. Jego entropia wynosi 1,4591. To jest H ₀ .

Ciąg cdefghma więcej entropii niż aabcab. Możemy to wiedzieć bez obliczania, ponieważ dla danej liczby znaków entropia jest zmaksymalizowana, gdy wszystkie częstotliwości są równe. Rzeczywiście, entropia H ₁ wynosi 2,5850.

Ciąg cdefghiponownie ma więcej entropii niż poprzedni. Możemy teraz bez obliczeń, ponieważ dodanie nieistniejącej postaci zawsze zwiększa entropię. Rzeczywiście, H ₂ wynosi 2,8074.

Gdyby następna struna była 42łańcuchem, łańcuch byłby nieprawidłowy, ponieważ H ₃ byłby 1, mniejszy niż 2,8074.

Z drugiej strony, gdyby sekwencja kontynuowała wytwarzanie ciągów o wzrastającej entropii z granicą H _∞ = 3, wynik wynosiłby (3-1,4597) / 6 = 0,2567.

Podziękowanie

Dzięki

• @xnor za pomoc w poprawieniu wyzwania, a w szczególności za przekonanie mnie, że nieskończone łańcuchy rosnącej entropii uzyskane w wyniku iteracyjnego wykonania są rzeczywiście możliwe;

• @flawr, aby uzyskać kilka sugestii, w tym modyfikację funkcji score i napisanie bardzo przydatnego fragmentu;

• @Angs za wskazanie istotnej wady w poprzedniej definicji funkcji score;

• @Dennis za poprawkę we fragmencie kodu JavaScript;

• @ETHproductions dla kolejnej poprawki we fragmencie;

• @PeterTaylor dla poprawki w definicji entropii.

Snippet do obliczania entropii

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>

Galaretka, 0,68220949

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

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

Użyłem długich podwójnych do obliczenia H ₉₀ . Pływaki podwójnej precyzji nieprawidłowo zgłosiły, że H ₄₇ <H ₄₆

Pierwszy program zostanie wydrukowany

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

gdzie …służy jako symbol zastępczy dla wszystkich znaków Unicode z punktami kodowymi między 100 000 i 1,000,000 . Rzeczywista długość wynosi 900 031 znaków.

Program sekund zostanie wydrukowany

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

który z kolei drukuje

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

itp.

Żaden z tych programów nie działa w tłumaczu online, który ma limit wyjściowy 100 KB . Jeśli jednak zmodyfikujemy program do drukowania 0123456789zamiast wyżej wymienionych 900 000 znaków Unicode, możesz wypróbować go online!

MATLAB, 9,6923e-005 0,005950967872272

H0 =  2.7243140535197345, Hinf = 4.670280547752703, L0 = 327

Ta nowa wersja jest ulepszoną wersją pierwszego „dowodu koncepcji”. W tej wersji mam świetny wzrost wyniku od pierwszej iteracji. Osiągnięto to poprzez „wysadzenie” wyjścia pierwszego programu, który jest replikowany przez wszystkie kolejne. Potem również próbowałem znaleźć minimum H0, dodając jak najczęstszy symbol kodu tak wiele razy, jak to możliwe. (Miało to oczywiście limit, ponieważ nie tylko zmniejsza się, H0ale także zwiększa L0w tym samym czasie. Możesz zobaczyć rozwój wyniku wykreślony w stosunku do wielkości programu, w którym rozmiar jest zróżnicowany, po prostu dodając lub usuwając 1.) Kolejne iteracje nadal są równoważne poprzedniej wersji poniżej.

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

Poprzednia wersja:

H0 = 4.22764479010266, Hinf = 4.243346286312808, L0 = 162

Poniższy kod jest inspirowany quine Matlaba . Zasadniczo wysyła tylko dwa razy . Chodzi o to, że dla każdej iteracji mamy nlinie kodu i n-1symbole nowej linii \n. Tak więc, gdy nzbliżamy się do nieskończoności, stosunek linii kodu do znaków nowej linii zbliża się do 1, a jednocześnie gwarantuje to, że mamy ściśle monotonowy wzrost entropii. Oznacza to również, że możemy łatwo obliczyć Hinf, biorąc pod uwagę kod zerowej generacji z równie wieloma nowymi liniami jak liniami kodu. (Który można eksperymentalnie potwierdzić, ponieważ zbiega się dość szybko).

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