Konstanta Chaitin normal?

Menurut sumber ini, konstanta Chaitin $\Omega$ itu normal.

Setiap probabilitas penghentian adalah bilangan real normal dan transendental yang tidak dapat dihitung, yang berarti bahwa tidak ada algoritma untuk menghitung digitnya. Memang, setiap probabilitas penghentian adalah acak Martin-Löf, yang berarti tidak ada algoritma apa pun yang dapat dengan andal menebak angka-angkanya.

Sumber (Wikipedia)

Selanjutnya, definisi normal adalah bahwa setiap digit terjadi dengan probabilitas yang sama $1/b$. Dan bahwa setiap duet digit terjadi dengan probabilitas dan setiap kembar tiga terjadi dengan probabilitas dan seterusnya.$1/b^2$$1/b^3$

Omega Chaitin dihitung melalui

$\Omega = \sum_{p \in halts} 2^{-|p|}$

Menulis dalam biner, kami memperoleh daftar 0 dan 1. Misalnya,$\Omega$

2^-1=0.1 +
2^-2=0.01 +
2^-3=0.001 +
~skip 2^-4 as it does not halt
2^-5=0.00001 +
...
=\Omega
=0.11101...

Jelas, kita dapat melihat bahwa posisi masing-masing bit sesuai dengan keadaan terputusnya program panjang yang sesuai dengan bit.

Inilah yang saya perjuangkan

Jika memang normal, maka itu berarti bahwa tepat 50% dari program berhenti dan tepatnya 50% tidak. Ini tampaknya sangat berlawanan dengan intuisi.$\Omega$

Sebagai contoh, misalkan saya membuat program java dengan menggabungkan satu karakter secara acak. Mayoritas dari mereka, saya kira lebih dari 99,99% bahkan tidak akan dikompilasi. Apakah ini tidak berarti bahwa setidaknya 99,99% dari mereka tidak akan berhenti? Bagaimana kita membenarkan bahwa setengah akan berhenti dan setengah lagi tidak, karena normal.$\Omega$

Atau apakah wikipedia salah tentang normal?$\Omega$

Berbeda dengan contoh Anda, konstanta Chaitin tidak didefinisikan sebagai berikut:

Sebagai gantinya, ada satu set $\Pi \subseteq \{0,1\}^*$dari program yang diizinkan yang bebas awalan (tidak ada string adalah awalan dari string lain). Setiap program di$\Pi$legal (ini meniadakan contoh Java Anda). Jika program pengkodean di unary maka memang demikian halnya$n$Program th memiliki panjang $n$, dan kemudian definisi Anda tentang $\Omega$bekerja. Tetapi untuk pengkodean lainnya, definisi$\Omega$ adalah

Konstanta Chaitin secara algoritmik acak : kompleksitas (awalan) Kolmogorov yang pertama$n$ bit adalah $n - O(1)$. Untuk menunjukkan ini, perhatikan dulu itu$\Omega_n$, pertama $n$ bit $\Omega$, cukup untuk menentukan apakah suatu program panjang $n$ (di bawah pengkodean $\Pi$) berhenti atau tidak. Memang, sebagai pecahan,$\Omega_n \leq \Omega < \Omega_n + 2^{-n}$. Jalankan semua program secara paralel, dan kapan saja$p$ berhenti, tambahkan $2^{-|p|}$ ke beberapa counter $C$(diinisialisasi pada nol). Akhirnya$C \geq \Omega_n$ (sejak $C \to \Omega$dari bawah). Pada titik ini, jika program input panjang$n$ tidak berhenti, maka Anda tahu bahwa itu tidak berhenti, karena sebaliknya $\Omega \geq C + 2^{-n} \geq \Omega_n + 2^{-n}$.

Mengingat ini, anggap itu untuk beberapa $K>0$ dan tak terhingga banyaknya $n$, Anda bisa menghitung $\Omega_n$ menggunakan $n - K$bit. Untuk masing-masing$n$, Anda dapat menemukan string yang kompleksitas Kolmogorov lebih besar dari $n$, dengan mempertimbangkan output dari semua program penghentian yang paling panjang $n$. Cukup besar$K$, hasilnya adalah program panjang paling banyak $n$ untuk menghitung string yang kompleksitas Kolmogorovnya lebih dari $n$. Kontradiksi ini membuktikan hal itu bagi sebagian orang$K$, kompleksitas Kolmogorov dari $\Omega_n$ setidaknya $n-K$.

Keacakan algoritma dari $\Omega$menyiratkan, khususnya, bahwa frekuensi 0s dan 1s dalam ekspansi binernya cenderung 1/2. Sungguh, anggap itu untuk beberapa (rasional)$\epsilon > 0$ ada banyak sekali tak terhingga $n$ sedemikian sehingga fraksi 1s di $\Omega_n$ paling banyak $1/2-\epsilon$. Karena hanya ada paling banyak$2^{h(1/2-\epsilon)n}$ string dengan paling banyak $1/2-\epsilon$ banyak 1, kita bisa kompres $\Omega_n$ untuk ukuran $h(1/2-\epsilon)n + 2\log n + C_\epsilon$ (konstan $C_\epsilon$ tergantung pada $\epsilon$ karena program perlu tahu $\epsilon$). Namun ini$n - \omega(1)$, bertentangan dengan keacakan algoritmik dari $\Omega$.

Kesalahan Anda ada pada baris berikut:

Jika $\Omega$ memang normal, maka itu berarti bahwa tepat 50% dari program berhenti dan tepatnya 50% tidak.

Nggak. Bukan itu arti "normal". Atau, dengan kata lain: Definisikan$d_0(n)$ menjadi jumlah bit yang merupakan 0, di pertama $n$ bit dari ekspansi basis-2 dari $\Omega$. Mengatakan itu$\Omega$adalah yang normal menyiratkan bahwa

Dengan kata lain, "normal" adalah gagasan asimptotik. Ini berarti bahwa ketika Anda melihat cukup jauh ke dalam bit$\Omega$, rata-rata sekitar setengahnya adalah 0. (Demikian pula, sekitar setengah dengan menjadi 1.)

Namun, ini tidak mengatakan apa-apa tentang beberapa bit pertama $\Omega$. Misalnya, tidak ada implikasi bahwa ekspansi biner$\Omega$ dimulai dengan 0,01 ... atau apa pun - dan tidak ada implikasinya $\Omega$ dekat dengan 1/2. $\Omega$mungkin mendekati 0, atau mendekati 1, atau di mana saja di antaranya; itu tidak bertentangan dengan normal, dan menjadi normal tidak menyiratkan apa pun tentang seberapa besar$\Omega$ adalah.