Generator angka yang benar-benar acak: Turing dapat dihitung?

Saya mencari jawaban pasti untuk apakah generasi angka "benar-benar acak" Turing dapat dihitung. Saya tidak tahu bagaimana mengucapkannya dengan tepat. Pertanyaan StackExchange tentang "algoritma efisien untuk pembuatan angka acak" ini hampir menjawab pertanyaan saya. Charles Stewart mengatakan dalam jawabannya, "itu [Martin-Löf keacakan] tidak dapat dihasilkan oleh mesin." Ross Snider mengatakan, "segala proses deterministik (seperti Mesin Turing / Registrasi) tidak dapat menghasilkan angka acak 'filosofis' atau 'benar'." Apakah ada gagasan yang jelas dan diterima tentang apa yang merupakan generator angka yang benar-benar acak? Dan jika demikian, apakah diketahui bahwa ia tidak dapat dihitung oleh Mesin Turing?

Mungkin mengarahkan saya ke literatur yang relevan sudah cukup. Terima kasih atas bantuan yang Anda berikan!

Edit. Terima kasih kepada Ian dan Harun untuk jawaban yang luas! Saya relatif tidak bersekolah di daerah ini, dan saya berterima kasih atas bantuannya. Jika saya dapat sedikit memperluas pertanyaan dalam lampiran ini: Apakah ini masalah TM dengan akses ke sumber acak (oracle?), Dapat menghitung fungsi yang tidak bisa dilakukan TM klasik?

Saya bergabung dengan diskusi agak terlambat, tetapi saya akan mencoba menjawab beberapa pertanyaan yang diajukan sebelumnya.

Pertama, seperti yang diamati oleh Aaron Sterling, penting untuk terlebih dahulu memutuskan apa yang kita maksud dengan angka "benar-benar acak", dan terutama jika kita melihat sesuatu dari kompleksitas komputasi atau perspektif komputabilitas.

Akan tetapi, saya berpendapat bahwa dalam teori kompleksitas, orang-orang terutama tertarik pada pseudo -randomness, dan pseudo -random generator, yaitu fungsi dari string ke string sehingga distribusi urutan output tidak dapat dipisahkan dari distribusi seragam oleh beberapa proses yang efisien (di mana beberapa arti dari efisien dapat dipertimbangkan, misalnya polytime computable, polinomial-size circuits dll). Ini adalah area penelitian yang indah dan sangat aktif, tetapi saya pikir sebagian besar orang akan setuju bahwa objek yang dipelajari tidak benar-benar acak, cukup bahwa mereka hanya terlihat acak (maka istilah "semu").

Dalam teori komputabilitas, sebuah konsensus telah muncul untuk apa yang seharusnya menjadi gagasan yang baik tentang "keacakan benar", dan memang gagasan keacakan Martin-Lof yang berlaku (yang lain telah diusulkan dan menarik untuk dipelajari tetapi tidak telanjang semua). properti bagus Martin-Lof memiliki keacakan). Untuk menyederhanakan masalah, kami akan mempertimbangkan keacakan untuk sekuens biner tak terbatas (objek lain seperti fungsi dari string ke string dapat dengan mudah dikodekan oleh urutan seperti itu).

Urutan biner tak terbatas adalah Martin-Löf acak jika tidak ada proses yang dapat dihitung (bahkan jika kami mengizinkan proses ini dapat dihitung dalam waktu tiga kali lipat atau lebih tinggi) dapat mendeteksi cacat keacakan.$\alpha$

(1) Apa yang kita maksud dengan "kesalahan acak"? Bagian yang mudah: itu adalah satu set ukuran 0, yaitu properti yang hampir semua urutan tidak memiliki (di sini kita berbicara tentang Lebesgue mengukur yaitu ukuran di mana setiap bit memiliki probabilitas menjadi 0 secara independen dari semua lainnya bit). Contoh dari cacat semacam itu adalah "memiliki 1/3 nol nol tanpa gejala dan 2/3 nol", yang melanggar hukum angka besar. Contoh lain adalah "untuk setiap n, bit 2n pertama α terdistribusi sempurna (sebanyak nol sebagai yang)". Dalam hal ini hukum bilangan besar disahkan, tetapi bukan teorema batas pusat. Dll.$1/2$$0$$\alpha$
(2) Bagaimana suatu proses yang dapat dikomputasi menguji bahwa suatu urutan bukan milik satu set ukuran 0 tertentu? Dengan kata lain, set ukuran 0 apa yang dapat dijelaskan secara komputatif? Inilah tepatnya tes Martin-Löf. Tes Martin-Löf adalah prosedur yang dapat dikomputasi, yang diberi input k, dapat dihitung (yaitu, melalui mesin Turing dengan input ) menghasilkan urutan string w k , 0 , w k , 1 , ... sedemikian sehingga set U k urutan yang tak terbatas mulai dengan salah satu dari mereka w k , i memiliki ukuran paling 2 - $k$$w_{k,0}$$w_{k,1}$$U_k$$w_{k,i}$$2^{-k}$(jika Anda suka topologi, perhatikan bahwa ini adalah set terbuka di topologi produk untuk set urutan biner yang tak terbatas). Kemudian set memiliki ukuran 0 dan disebut sebagai Martin-LOF nullset . Kita sekarang dapat mendefinisikan keacakan Martin-Löf dengan mengatakan bahwa urutan biner tak terbatas α adalah Martin-Löf acak jika itu bukan milik nullset Martin-Löf . $G=\bigcap_k U_k$$0$$\alpha$

Definisi ini mungkin tampak teknis tetapi diterima secara luas sebagai definisi yang tepat karena beberapa alasan:

• itu cukup efektif, yaitu definisinya melibatkan proses yang dapat dihitung
• itu cukup kuat: properti "hampir pasti" yang mungkin Anda temukan dalam buku teks teori probabilitas (hukum angka besar, hukum iterasi logaritma, dll) dapat diuji dengan tes Martin-Löf (walaupun terkadang sulit untuk dibuktikan)
• telah diusulkan secara independen oleh beberapa orang menggunakan definisi yang berbeda (khususnya definisi Levin-Chaitin menggunakan kompleksitas Kolmogorov); dan fakta bahwa mereka semua mengarah ke konsep yang sama adalah petunjuk bahwa itu harus menjadi gagasan yang benar (sedikit seperti gagasan fungsi yang dapat dihitung, yang dapat didefinisikan melalui mesin Turing, fungsi rekursif, lambda-kalkulus, dll.)
• teori matematika di baliknya sangat bagus! lihat tiga buku unggulan Pengantar Kompleksitas Kolmogorov dan Penerapannya (Li dan Vitanyi), Keacakan dan Kompleksitas Algoritma (Downey dan Hirschfeldt) Komputasi dan Keacakan (Nies).

Seperti apakah urutan acak Martin-Löf? Nah, ambil koin yang seimbang sempurna dan mulai membalikkannya. Di setiap flip, tulis 0 untuk kepala dan 1 untuk ekor. Lanjutkan sampai akhir waktu. Seperti itulah urutan Martin-Löf :-)

Sekarang kembali ke pertanyaan awal: apakah ada cara yang dapat dihitung untuk menghasilkan urutan acak Martin-Löf? Secara intuitif jawabannya harus TIDAK , karena jika kita dapat menggunakan proses yang dapat dihitung untuk menghasilkan urutan , maka kita pasti dapat menggunakan proses yang dapat dihitung untuk menggambarkan singleton { α }, sehingga α tidak acak. Secara formal ini dilakukan sebagai berikut. Misalkan urutan α dapat dihitung. Pertimbangkan mengikuti tes Martin-LOF: untuk semua k , hanya output awalan sebuah k dari α panjang k , dan tidak ada lagi. Ini memiliki ukuran paling banyak (pada kenyataannya, tepatnya) 2 - $\alpha$$\alpha$$\alpha$$\alpha$$k$$a_k$$\alpha$$k$$2^{-k}$, Dan persimpangan set seperti dalam definisi persis { α }. QED !!$U_k$${\alpha}$

Faktanya urutan acak Martin-Löf dapat dihitung dalam arti yang jauh lebih kuat: jika beberapa perhitungan oracle dengan oracle β (yang itu sendiri merupakan urutan biner tak terbatas) dapat menghitung α , maka untuk semua bit n , n - O ( 1 ) dari β diperlukan untuk menghitung n bit pertama dari α (ini sebenarnya adalah karakterisasi keacakan Martin-Löf, yang sayangnya jarang dinyatakan seperti dalam literatur).$\alpha$$\beta$$\alpha$$n$$n-O(1)$$\beta$$n$$\alpha$

Ok, sekarang bagian "edit" dari pertanyaan Joseph: Apakah ini masalah TM yang memiliki akses ke sumber acak (oracle?), Dapat menghitung fungsi yang tidak bisa dilakukan TM klasik?

Dari perspektif komputabilitas, jawabannya adalah "ya dan tidak". Jika Anda diberi akses ke sumber acak sebagai oracle (di mana output disajikan sebagai urutan biner tak terbatas), dengan probabilitas 1 Anda akan mendapatkan oracle acak Martin-Löf, dan seperti yang kita lihat sebelumnya, Martin-Löf acak menyiratkan non- dapat dihitung, sehingga cukup untuk menampilkan oracle itu sendiri! Atau jika Anda menginginkan fungsi , Anda dapat mempertimbangkan fungsi f yang untuk semua n memberi tahu Anda berapa banyak nol yang ada di antara n bit pertama dari oracle Anda. Jika oracle adalah Martin-Löf acak, fungsi ini tidak dapat dikomputasi.$f: \mathbb{N} \rightarrow \mathbb{N}$$f$$n$$n$

Tapi tentu saja Anda mungkin berpendapat bahwa ini curang: memang, untuk oracle yang berbeda kita mungkin mendapatkan fungsi yang berbeda, jadi ada masalah yang tidak dapat direproduksi. Oleh karena itu cara lain untuk memahami pertanyaan Anda adalah sebagai berikut: apakah ada fungsi yang tidak dapat dihitung, tetapi yang dapat "dihitung dengan probabilitas positif", dalam arti bahwa ada mesin Turing dengan akses ke oracle acak yang, dengan probabilitas positif (selama oracle), menghitung f . Jawabannya tidak, karena teorema Sacks yang buktinya cukup sederhana. Sebenarnya itu terutama telah dijawab oleh Robin Kothari: jika probabilitas untuk TM menjadi benar lebih besar dari 1/2, maka seseorang dapat mencari semua n di semua kemungkinan perhitungan oracle dengan input $f$$f$$n$$n$dan temukan output yang mendapat "suara terbanyak", yaitu yang dihasilkan oleh seperangkat nubuat berukuran lebih dari 1/2 (ini dapat dilakukan secara efektif). Argumen bahkan meluas ke probabilitas yang lebih kecil: anggaplah output TM dengan probabilitas ϵ > 0 . Dengan teorema kepadatan Lebesgue, ada string berhingga σ sehingga jika kita memperbaiki bit pertama oracle menjadi tepat σ , dan kemudian mendapatkan bit lainnya secara acak, maka kita menghitung f dengan probabilitas setidaknya 0,99. Dengan mengambil σ seperti itu , kita dapat menerapkan argumen di atas lagi.$f$$\epsilon >0$$\sigma$$\sigma$$f$$\sigma$

Ada (mungkin) perbedaan yang harus dibuat antara "Turing computable" dan "efektif computable" untuk menjawab pertanyaan Anda. Jika seseorang mendefinisikan "proses acak" sebagai "proses yang tidak dapat diprediksi, tidak peduli sumber daya apa pun yang kita miliki," dan seseorang mendefinisikan "proses deterministik" sebagai "proses yang dapat diprediksi, diberi input dan akses ke (mungkin banyak) sumber daya, "maka tidak ada fungsi komputasi Turing yang dapat dilakukan secara acak, karena jika kita mengetahui mesin Turing dan mensimulasikannya, kita selalu dapat memprediksi hasil dari" percobaan "proses selanjutnya.

Dalam kerangka kerja ini, tes Martin-Lof dapat dilihat sebagai proses deterministik, dan definisi urutan acak adalah urutan yang perilakunya tidak diprediksi oleh tes Martin-Lof / Turing yang dapat dihitung / proses deterministik Turing.

Namun, ini menimbulkan pertanyaan: "Apakah urutan acak dapat dihitung secara efektif, dalam kehidupan nyata?" Faktanya, ada industri di sini. Ada CD yang diterbitkan dengan miliaran bit acak (?) Pada mereka yang digunakan untuk melakukan simulasi komputer sistem fisik, dll. CD ini menjamin bahwa urutan bit mereka melewati serangkaian tes Martin-Lof. Buku The Drunkard's Walk: How Randomness Rules Our Lives memberikan penjelasan umum tentang masalah ini, secara lebih rinci.

Poin yang tidak relevan: Saya menikmati kolom Anda. :-)

Secara intuitif, "acak" berarti "tidak dapat diprediksi", dan setiap urutan yang dihasilkan oleh mesin Turing dapat diprediksi dengan menjalankan mesin, sehingga mesin Turing tidak dapat menghasilkan angka "benar-benar acak". Ada sejumlah definisi formal dari urutan acak (keacakan hanya benar-benar masuk akal ketika panjang sebuah string pergi hingga tak terbatas), yang semuanya pada dasarnya setara. Mungkin yang paling alami adalah Martin-Lof randomness, yang berarti bahwa sekuens melewati semua kemungkinan uji statistik yang dapat dihitung untuk stochasticity, dan Chaitin random yang berarti bahwa semua tahapan awal tidak dapat dimampatkan (lebih khusus, memiliki kompleksitas Kolmogorov yang tinggi). Dalam kedua definisi ini tidak dapat dihitung untuk menghasilkan urutan acak dan untuk mengenalinya. Lihat buku "Informasi dan Keacakan:

Siapa pun yang menganggap metode aritmatika menghasilkan angka acak, tentu saja, dalam keadaan berdosa. Karena, seperti yang telah ditunjukkan beberapa kali, tidak ada yang namanya bilangan acak - hanya ada metode untuk menghasilkan bilangan acak, dan prosedur aritmatika yang ketat tentu saja bukan metode seperti itu. - John von Neumann

Sepertinya tidak ada yang menjawab adendum Anda, jadi saya akan coba:

Jika saya dapat sedikit memperluas pertanyaan dalam lampiran ini: Apakah ini masalah TM dengan akses ke sumber acak (oracle?), Dapat menghitung fungsi yang tidak dapat dilakukan TM klasik?

Saya akan mencoba membuat pertanyaan lebih tepat, dan kemudian menjawabnya. (Versi saya mungkin tidak sesuai dengan yang Anda pikirkan, jadi beri tahu saya jika tidak.)

Kami memiliki TM deterministik dengan akses ke generator angka acak. TM ini sekarang menghitung beberapa fungsi (fungsi aktual, yaitu, peta deterministik dari ruang input ke ruang output) memanfaatkan generator nomor acak dalam beberapa cara.

Jadi apakah TM dengan akses ke keacakan diizinkan untuk membuat kesalahan? Jika tidak, maka DTM harus memberikan jawaban yang benar tidak peduli bit acak apa yang diberikan. Dalam hal ini bit acak tidak diperlukan, karena Anda bisa mengambil string acak menjadi 00000 ...

$f_i(x,r)$$f_i$$r$

Mengenai "pertanyaan edit" Anda: itu membuat perbedaan besar jika Anda bertanya tentang komputabilitas atau kompleksitas. Jika ada batasan kompleksitas pada TM, maka Anda mendapatkan apa yang disebut model oracle acak . Jika TM dapat menggunakan sumber daya yang besar tapi terbatas secara sewenang-wenang, maka Anda berada di dunia keacakan relatif : ada hierarki acak dari oracle, seperti halnya derajat Turing. (Poin samping: salah satu kritik terkenal Koblitz dan Menze adalah tentang penggunaan model ramalan acak, jadi meta-pertanyaan Anda menyentuh debat akademik baru-baru ini.)

Saya masih mencoba memahami pertanyaan Anda yang dimodifikasi, terutama apa yang membatasi Anda pada TM. Jadi, sementara jawaban ini mungkin tidak mendapatkan apa yang Anda inginkan, mungkin ini akan membantu mempersempit hal-hal.

Kita tahu bahwa ada hasil ketidakmungkinan tanpa syarat untuk mendekati dengan faktor subeksponensial volume benda cembung secara deterministik (ini adalah hasil lama oleh Bárány dan Füredi ). Sebaliknya, kita bisa mendapatkan FPRAS untuk masalah ini menggunakan sampling. Apakah ini contoh pemisahan yang Anda cari?