Dan khususnya hukum kedua : entropi sistem terisolasi meningkat seiring waktu .

Untuk tantangan ini,

• " Sistem terisolasi " akan dianggap sebagai program atau fungsi (disingkat "program" mulai sekarang);
• Berlalunya " waktu " akan sesuai dengan eksekusi yang berulang dari output program , dianggap sebagai program baru;
• " Entropi " akan dianggap sebagai entropi orde pertama Shannon (akan didefinisikan di bawah), yang merupakan ukuran seberapa beragam karakter string.

Tantangan

Program Anda harus menghasilkan string yang tidak kosong yang ketika dieksekusi sebagai program dalam bahasa yang sama menghasilkan string dengan lebih banyak entropi daripada yang sebelumnya. Mengulangi proses eksekusi-output yang tak terhingga ini harus menghasilkan urutan nilai entropi yang meningkat secara ketat .

String dapat berisi karakter Unicode 9.0 . Urutan string harus deterministik (sebagai lawan acak).

The entropi untuk string yang diberikan akan didefinisikan sebagai berikut. Identifikasi karakter uniknya dan jumlah kemunculannya dalam string. Frekuensi p _i dari karakter unik ke- i adalah jumlah kemunculan karakter tersebut dibagi dengan panjang string. Entropi itu kemudian

di mana jumlahnya adalah seluruh karakter unik string. Secara teknis, ini sesuai dengan entropi dari variabel acak diskrit dengan distribusi yang diberikan oleh frekuensi yang diamati dalam string.

Mari H _k menyatakan entropi dari string yang dihasilkan oleh k Program -th, dan biarkan H ₀ menyatakan entropi dari kode program awal ini. Juga, biarkan L ₀ menunjukkan panjang program awal dalam karakter. Urutan { H _k } adalah monoton sesuai persyaratan tantangan, dan dibatasi (karena jumlah karakter yang ada terbatas). Karena itu ia memiliki batas, H _∞ .

The skor pengajuan akan menjadi ( H _∞ - H ₀ ) / L ₀ :

• Pembilangnya, H _∞ - H ₀ , mencerminkan sejauh mana kode Anda "mematuhi" hukum peningkatan entropi selama rentang waktu tak terbatas.
• Denonimator, L ₀ , adalah panjang kode awal dalam karakter (bukan dalam byte).

Kode dengan skor tertinggi menang . Ikatan akan diselesaikan untuk pengajuan / edit paling awal.

Untuk menghitung entropi string, Anda dapat menggunakan JavaScript potongan (courtesy of @flawr dan dengan koreksi oleh @Dennis dan @ETHproductions ) pada akhir posting ini.

Jika mendapatkan batas H _∞ sulit dalam kasus spesifik Anda, Anda dapat menggunakan batas bawah apa pun, misalnya H ₂₀ , untuk menghitung skor (jadi Anda akan menggunakan ( H ₂₀ - H ₀ ) / L ₀ ). Tetapi bagaimanapun juga, urutan entropi yang tak terbatas harus meningkat secara ketat.

Harap sertakan penjelasan atau bukti singkat bahwa urutan entropi meningkat, jika itu tidak terbukti.

Contoh

Dalam bahasa fiksi, pertimbangkan kode aabcab, yang saat dijalankan menghasilkan string cdefgh, yang saat dijalankan menghasilkan cdefghi, yang ...

Karakter unik dari kode asli adalah a, bdan c, dengan frekuensi masing-masing 3/6, 2/6 dan 1/6. Entropinya adalah 1,4591. Ini adalah H ₀ .

String cdefghmemiliki lebih banyak entropi daripada aabcab. Kita dapat mengetahui ini tanpa menghitungnya karena untuk sejumlah karakter tertentu entropi dimaksimalkan ketika semua frekuensinya sama. Memang, entropi H ₁ adalah 2,5850.

String cdefghilagi memiliki lebih banyak entropi daripada yang sebelumnya. Kita sekarang dapat tanpa menghitung karena menambahkan karakter yang tidak ada selalu meningkatkan entropi. Memang, H ₂ adalah 2,8074.

Jika string berikutnya adalah 42rantai akan menjadi tidak valid, karena H ₃ akan menjadi 1, lebih kecil dari 2,8074.

Jika, di sisi lain, urutan melanjutkan menghasilkan string peningkatan entropi dengan batas H _∞ = 3, skornya adalah (3−1.4597) / 6 = 0.2567.

Ucapan Terima Kasih

Terimakasih untuk

• @ xnor atas bantuannya memperbaiki tantangan, dan khususnya untuk meyakinkan saya bahwa rantai tak terbatas peningkatan entropi yang diperoleh dari eksekusi berulang memang mungkin;

• @ flawr untuk beberapa saran, termasuk memodifikasi fungsi skor, dan untuk menulis cuplikan yang sangat berguna;

• @Angs untuk menunjukkan kelemahan penting dalam definisi fungsi skor sebelumnya;

• @Dennis untuk koreksi dalam cuplikan JavaScript;

• @ETHproduk untuk koreksi lain dalam cuplikan;

• @PeterTaylor untuk koreksi dalam definisi entropi.

Cuplikan untuk menghitung entropi

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>

Jelly, 0,68220949

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

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

Saya menggunakan ganda panjang untuk menghitung H ₉₀ . Ketelitian ganda mengapung secara tidak benar melaporkan bahwa H ₄₇ <H ₄₆

Program pertama dicetak

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

di mana …berfungsi sebagai pengganti untuk semua karakter Unicode dengan titik kode antara 100.000 dan 1.000.000 . Panjang sebenarnya adalah 900.031 karakter.

Program detik dicetak

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

yang, pada gilirannya, mencetak

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

dll.

Tidak satu pun dari program ini yang berfungsi dalam juru bahasa online, yang memiliki batas keluaran 100 KB . Namun, jika kami memodifikasi program untuk mencetak 0123456789alih-alih 900.000 karakter Unicode yang disebutkan di atas , Anda dapat Coba online!

MATLAB, 9.6923e-005 0.005950967872272

H0 =  2.7243140535197345, Hinf = 4.670280547752703, L0 = 327

Versi baru ini adalah versi perbaikan dari "bukti konsep" pertama. Dalam versi ini saya mendapatkan peningkatan skor besar dari iterasi pertama. Ini dicapai dengan "meledakkan" output dari program pertama, yang direplikasi oleh semua yang berikutnya. Kemudian saya juga mencoba mencari minimal H0dengan hanya menambahkan simbol kode yang paling umum sebanyak mungkin. (Ini jelas memiliki batas, karena tidak hanya menurun H0tetapi juga meningkat L0pada saat yang sama. Anda dapat melihat perkembangan skor diplot terhadap ukuran program di mana ukurannya bervariasi dengan hanya menambah atau menghapus 1.) Berikutnya iterasi masih setara dengan versi sebelumnya di bawah ini.

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

Versi sebelumnya:

H0 = 4.22764479010266, Hinf = 4.243346286312808, L0 = 162

Kode berikut diilhami oleh matlab quine . Ini pada dasarnya hanya menampilkan sendiri lagi dua kali . Petunjuknya adalah bahwa untuk setiap iterasi kami memiliki nbaris kode dan n-1simbol baris baru \n. Jadi, ketika nmendekati infinity, rasio garis kode ke baris baru mendekati 1, dan pada saat yang sama ini menjamin bahwa kita memiliki pertumbuhan entropi yang sangat monoton. Itu juga berarti kita dapat dengan mudah menghitung Hinfdengan hanya mempertimbangkan kode generasi ke-nol dengan baris baru yang sama banyaknya sebagai garis kode. (Yang mana dapat secara eksperimental mengkonfirmasi, karena konvergennya cukup cepat.)

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