Pertanyaan tentang simulasi satu model dengan model lainnya. Ini termasuk simulasi realitas dalam model apa pun, atau simulasi model mesin dengan mesin Turing.
Saya mencari penjelasan tentang bagaimana seseorang dapat membuktikan bahwa dua model perhitungan adalah setara. Saya telah membaca buku-buku tentang masalah ini kecuali bahwa bukti kesetaraan dihilangkan. Saya punya ide dasar tentang apa artinya dua model perhitungan menjadi setara (tampilan...
Menurut artikel Wikipedia ini , tata bahasa tidak terbatas setara dengan mesin Turing. Artikel tersebut mencatat bahwa saya dapat mengubah mesin Turing apa pun menjadi tata bahasa yang tidak dibatasi, tetapi hanya menunjukkan cara mengubah tata bahasa menjadi mesin Turing. Bagaimana saya melakukan...
Biarkan menjadi fungsi tetap yang dapat dibangun-waktu.fff Hasil simulasi universal klasik untuk TMs (Hennie dan Stearns, 1966) menyatakan bahwa ada dua-tape TM sedemikian rupa sehingga diberikanUUU deskripsi dari TM , dan⟨M⟩⟨M⟩\langle M \rangle string input ,xxx dijalankan untuk langkah dan...
Atas pertanyaan tentang penghitungan inversi ini , saya menemukan makalah yang membuktikan batas bawah pada kompleksitas ruang untuk semua algoritma streaming (pasti) . Saya telah mengklaim bahwa batasan ini meluas ke semua algoritma waktu linier. Ini agak berani seperti pada umumnya, algoritma...
Tujuannya adalah membuat DFA dari ekspresi reguler dan menggunakan "Exp reguler> NFA> Konversi DFA" bukan opsi. Bagaimana seharusnya orang melakukan itu? Saya mengajukan pertanyaan ini kepada profesor kami tetapi dia mengatakan kepada kami bahwa kami dapat menggunakan intuisi dan dengan baik...
Di tempat kerja saya ditugaskan untuk menyimpulkan beberapa jenis informasi tentang bahasa yang dinamis. Saya menulis ulang urutan pernyataan menjadi letekspresi bersarang , seperti: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z =>...
Apakah ada otomat seluler (dalam 2D) yang mensimulasikan gaya antara partikel?1/r1/r1/r Lebih khusus lagi, saya ingin tahu apakah mungkin, dengan aturan pembaruan lokal yang ketat, untuk memiliki dua objek (didefinisikan dalam model) menarik satu sama lain dengan kekuatan , di mana r adalah jarak...
Saya membaca Sipser dan saya merasa sulit untuk memahami apa prosesnya sehingga jika Anda memberi saya mesin Turing dengan kaset k, saya dapat memuntahkan mesin Turing yang setara dengan hanya satu kaset. Sebuah contoh akan menyenangkan. Sebenarnya, contoh yang menunjukkan bagaimana untuk pergi...
Pertanyaannya adalah latihan 1.9 dari buku Arora-Barak's Computational Complexity - A Modern Approach : Tentukan mesin RAM Turing menjadi mesin Turing yang memiliki memori akses acak. Kami meresmikan ini sebagai berikut: Mesin memiliki array A tak terbatas yang diinisialisasi ke semua kosong....
Saya mencoba menemukan jawaban dari dua pertanyaan tentang mesin Universal Turing. Bagaimana mesin Universal Turing dapat mensimulasikan mesin Turing jika mesin yang disimulasikan memiliki jumlah status yang lebih besar? Bagaimana mesin Universal Turing dapat mensimulasikan mesin Turing jika...
Apakah Mesin Turing yang diizinkan untuk membaca dan menulis simbol dari alfabet tak terbatas lebih kuat daripada TM biasa (itulah satu-satunya perbedaan, mesin masih memiliki sejumlah negara terbatas)? Intuisi tidak memberi tahu saya, karena Anda memerlukan jumlah negara tak terbatas untuk...
Apakah ada seperangkat aturan atau metode untuk mengubah tata bahasa bebas konteks apa pun menjadi automata push down? Saya sudah menemukan beberapa slide online tetapi saya tidak dapat memahaminya. Dalam slide 10 dia berbicara tentang beberapa aturan, adakah yang bisa
Diketahui bahwa logika temporal LTL, CTL, CTL * dapat diterjemahkan / disematkan ke dalam -calculus. Dengan kata lain, (modal) -calculus menggolongkan logika ini, (yaitu lebih ekspresif.)μμ\muμμ\mu Bisakah Anda jelaskan / arahkan saya ke makalah / buku yang menguraikan hal ini. Secara khusus,...
Saya punya sedikit masalah untuk memahami bukti Teorema Time Hierarchy (Hennie and Stearns, 1966) yang memastikan keberadaan bahasa yang dapat diterima dalam tetapi tidak dapat diterima dalam untuk fungsi apa pun , sehingga dapat dikonstruksi waktu
Ketika saya membaca tentang tesis Gereja-Turing, tampaknya menjadi klaim umum bahwa "realitas fisik dapat dihitung-Turing." Apa dasar dari klaim ini? Apakah ada hasil teoretis di sepanjang garis ini? Untuk konteks, saya adalah seorang peneliti yang bekerja pada simulasi fisik, jadi tentu saja saya...