Bisakah mesin Turing probabilistik menyelesaikan masalah penghentian?

Komputer yang diberi aliran tak terbatas dari bit yang benar-benar acak lebih kuat daripada komputer tanpa itu. Pertanyaannya adalah: apakah ini cukup kuat untuk menyelesaikan masalah penghentian?

Artinya, dapatkah komputer probabilistik menentukan apakah suatu program deterministik berhenti atau tidak ?

Contoh komputer probabilistik yang melakukan sesuatu yang deterministik tidak dapat: Pertimbangkan program kecil (panjangnya kurang dari satu kilobyte) yang menghasilkan string dengan kompleksitas Kolmogorov lebih besar dari satu gigabyte. The kompleksitas Kolmogorovstring adalah panjang dari program deterministik terpendek yang menghasilkan string itu. Dengan demikian, menurut definisi, program deterministik tidak dapat menghasilkan string yang kompleksitasnya lebih besar daripada panjangnya sendiri. Namun, jika diberi aliran infinite bit yang benar-benar acak, sebuah program kecil mampu mencapai tugas dengan 99,99999 ...% sukses hanya dengan menggemakan, katakanlah, 10 miliar bit acak dan berharap kompleksitas Kolmogorov dari bit tersebut cukup tinggi . Oleh karena itu, menghasilkan serangkaian kompleksitas Kolmogorov superior berada dalam cakrawala kemungkinan program probabilistik, tetapi sama sekali tidak mungkin untuk program deterministik.

Yang mengatakan, saya bertanya-tanya apakah mungkin untuk menggunakan bit yang benar-benar acak untuk memotong gergaji di masalah penghentian. Sebagai contoh, suatu algoritma dapat secara acak menghasilkan teorema dan membuktikan / menolak / membuangnya sampai cukup tahu untuk membuktikan / membantah bahwa program deterministik tertentu berhenti.

sunting: Saya baru menyadari beberapa hal yang saya tulis adalah omong kosong total, maaf untuk itu. Sekarang saya mengubah buktinya dan membuat definisi mesin probabilistik yang saya gunakan lebih tepat.

Saya tidak tahu apakah saya sudah benar definisi mesin Turing probabilistik: itu adalah mesin dengan rekaman tambahan yang dituliskan string tak terbatas yang tak terbatas, dan di samping itu berfungsi seperti mesin deterministik? Jika kita memperbaiki string yang tidak bisa dimampatkan, kelas yang kita dapatkan tampaknya tidak menarik.

Saya pikir kita dapat mendefinisikan mesin Turing probabilistik dalam beberapa cara. Saya akan menggunakan definisi yang tampaknya cukup alami (dan untuk mana bukti saya bekerja;) Mari kita mendefinisikan mesin probabilistik seperti itu: ia mendapatkan rekaman tambahan di mana beberapa string tak terbatas ditulis, kita mengatakan bahwa mesin ini memutuskan bahasa jika untuk setiap itu berhenti dan menerima dengan probabilitas , ketika probabilitas diambil alih string acak tambahan itu, dan untuk setiap itu berhenti dan menolak dengan probabilitas .x ∈ L > $L$$x \in L$ x∉L>$>\frac{1}{2}$$x \not \in L$$>\frac{1}{2}$

Kami sekarang akan menunjukkan bahwa jika ada mesin probabilistik yang memecahkan masalah berhenti untuk mesin deterministik, kita bisa menggunakannya untuk membangun mesin deterministik yang memecahkan masalah berhenti untuk mesin deterministik - dan kita tahu bahwa mesin seperti itu tidak bisa ada$P$$H$

Asumsikan seperti itu ada. Kita dapat membangun mesin deterministik yang mengambil input mesin probabilistik dengan beberapa input , yangM R $P$$M$$R$$x$

• berhenti dan terima jika dan hanya jika menerima (yaitu berhenti dan menerima pada lebih dari setengah string acak).x R $R$$x$$R$$x$
• menghentikan dan menolak jika dan hanya jika menolak (yaitu menghentikan dan menolak pada lebih dari setengah string acak).x R $R$$x$$R$$x$
• loop sebaliknya

Pada dasarnya, akan untuk semua mensimulasikan pada input dan pada setiap string dari sebagai awalan dari string pada pita acakSekarang:i ∈ 1 , 2 , . . . R x 0 , 1 i$M$$i \in 1, 2, ...$$R$$x$${{0,1}}^i$$R$

• jika untuk awalan panjang dihentikan dan diterima tanpa mencoba membaca lebih dari bit dari pita acak, berhenti dan menerima iRi$>\frac{1}{2}$$i$ $R$$i$$M$
• jika untuk awalan panjang dihentikan dan ditolak tanpa mencoba membaca lebih dari bit dari pita acak, berhenti dan ditolak iRi$>\frac{1}{2}$$i$ $R$$i$$M$
• jika tidak, menjalankan simulasi dengan .i : = i + $M$$i := i+1$

Kita harus meyakinkan diri kita sendiri sekarang, bahwa jika menerima (menolak) dengan probabilitas , maka untuk beberapa itu akan menerima (menolak) untuk awalan dari panjang dari string acak tanpa mencoba membaca lebih dari bit dari rekaman acak. Ini teknis, tetapi cukup mudah - jika kita berasumsi sebaliknya maka kemungkinan menerima (menolak) mendekati ketika menuju infinity, maka untuk beberapa itu harus .x p > $R$$x$ i>$p >\frac{1}{2}$$i$ iip>$>\frac{1}{2}$$i$$i$ iip>$p >\frac{1}{2}$$i$$i$$p >\frac{1}{2}$

Sekarang kita hanya mendefinisikan mesin deterministik kita menyelesaikan masalah penghentian (yaitu memutuskan apakah mesin deterministik yang diberikan menerima kata yang diberikan ) a sebagai . Perhatikan bahwa selalu berhenti, karena menentukan bahasa oleh mesin probabilistik kami didefinisikan sedemikian rupa sehingga salah satu dari keduanya selalu terjadi:N x H ( N , x ) = M ( P ( N , x ) ) M ( P ( N , x ) $H$$N$$x$$H(N,x) = M(P(N,x))$$M(P(N, x))$

• mesin berhenti dan menerima lebih dari setengah string acak
• mesin berhenti dan menolak untuk lebih dari setengah string acak.

Itu tergantung pada apa yang Anda maksud dengan algoritma probabilistik yang menentukan beberapa predikat.

Ada algoritma probabilistik trivial P sehingga, untuk mesin Turing deterministik M ,

• P ( M ) menerima dengan probabilitas nol jika M berhenti,
• P ( M ) tidak pernah menerima jika M tidak berhenti, dan
• P ( M ) pemberhentian dengan probabilitas 1 untuk setiap M .

Oleh karena itu, algoritma probabilistik P memecahkan masalah penghentian untuk mesin Turing deterministik dalam pengertian ini. (Di sini " M berhenti" berarti " M berhenti di input kosong.")

Namun, jika Anda memperkuat persyaratan dengan cara apa pun yang masuk akal, tidak mungkin Anda dapat menyelesaikan masalah penghentian untuk mesin Turing deterministik lagi. Sebagai contoh,

• Jika Anda memerlukan P ( M ) untuk berhenti selalu bukan hanya dengan probabilitas 1 , maka jelas bahwa P dapat disimulasikan oleh algoritma deterministik. (Lihat Wikipedia untuk penjelasan tentang perbedaan antara "selalu" dan "dengan probabilitas 1.")
• Jika Anda membuat kesalahan batas ketat dengan mengharuskan P ( M ) untuk berhenti dan memberikan jawaban yang benar dengan probabilitas lebih dari 1/2 untuk setiap M (yaitu, Anda tidak peduli jika P ( M ) tidak berhenti atau berhenti dan berikan jawaban yang salah di sisa kasus), maka P dapat disimulasikan oleh algoritma deterministik dengan menggunakan argumen yang dinyatakan dalam jawaban Karolina Sołtys .

Oleh karena itu, algoritma probabilistik tidak dapat menyelesaikan masalah penghentian untuk mesin Turing deterministik dalam pengertian ini.

Secara umum, jika Anda memiliki mesin Turing probabilistik memecahkan beberapa masalah keputusan, Anda selalu dapat mensimulasikan deterministik dengan menjalankan untuk setiap nilai yang mungkin dari keacakan dan keluaran jawaban mayoritas . Oleh karena itu, tidak ada mesin Turing probabilistik yang dapat menyelesaikan masalah keputusan yang tidak dapat dipastikan.P $P$$P$$P$

Saya pikir ini adalah makna dari komentar Raphael.

$A\subseteq\mathbb N$$A$

de Leeuw, K., Moore, EF, Shannon, CE, dan Shapiro, N. Computability oleh mesin probabilistik, studi Automata, hlm. 183–212. Sejarah studi matematika, no. 34. Princeton University Press, Princeton, NJ, 1956.

G. Karung, Derajat Ketidakpastian, Princeton University Press, 1963.