Saya membaca beberapa kali bahwa tidak mungkin membalik jawaban NDTM secara efisien. Namun, saya tidak mengerti mengapa. Misalnya, mengingat NDTM yang berjalan di , teks ini (bagian 3.3) menyatakan bahwa tidak jelas bagaimana NDTM dapat menentukan dalam waktu cara membalikkan
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...
OK, jadi inilah pertanyaan dari tes sebelumnya di kelas Teori Komputasi saya: Keadaan tidak berguna di TM adalah yang tidak pernah dimasukkan pada string input apa pun. Biarkan Buktikan bahwa tidak dapat ditentukan.USELESSTM={⟨M,q⟩∣q is a useless state in M}.USELESSTM={⟨M,q⟩∣q is a useless...
Saya memiliki masalah algoritmik berikut: Tentukan ruang Turing kompleksitas mengenali string DNA yang merupakan palindrom Watson-Crick. Palindrom Watson-Crick adalah string yang pelengkap terbalik adalah string asli. The pelengkap didefinisikan surat-bijaksana, terinspirasi oleh DNA: A...
Apakah menerima berarti bahwa TM akan membaca dan mengenali arang dari sel yang sedang dibacanya? Dan apakah TM berhenti jika inputnya dapat
Masalah memutuskan apakah input adalah palindrom atau tidak telah terbukti membutuhkan ruang pada mesin Turing. Namun, bahkan menyimpan input membutuhkan ruang jadi bukankah itu berarti bahwa semua mesin Turing memerlukan ruang ?Ω(logn)Ω(logn)\Omega(\log n)nnnΩ(n)Ω(n)\Omega(n) Tentu saja, tidak...
Saya telah melihat situs web yang mengaku "membuktikan" bahwa HTML5 + CSS Turing Lengkap. Saya telah melihat situs web yang mengaku "membuktikan" bahwa SQL adalah Turing Lengkap. Saya telah melihat banyak situs web yang dimaksudkan untuk "menjelaskan" apa artinya menjadi Lengkap...
Saya mendapatkan bukti pergi dari pencacah ke Mesin Turing (tetap menjalankan pencacah dan melihat apakah itu cocok dengan input) tetapi saya tidak melihat bagaimana cara lain bekerja. Menurut catatan dan buku saya (Pengantar Teori Komputasi - Sipser), untuk mendapatkan enumerator Turing dari...
Dalam analisis algoritma, kami mengasumsikan satu prosesor generik Random Access Machine (RAM). Sejauh yang saya tahu, mesin RAM tidak lebih efisien daripada mesin Turing. Semua algoritma dapat diimplementasikan di mesin Turing. Jadi pertanyaan saya adalah: Jika mesin Turing seefisien mesin RAM,...
Mesin Turing dan tata bahasa tidak terbatas adalah dua formalisme berbeda yang mendefinisikan bahasa RE. Beberapa bahasa RE dapat dipilih, tetapi tidak semua. Kita dapat mendefinisikan bahasa yang dapat diputuskan dengan mesin Turing dengan mengatakan bahwa bahasa dapat diputuskan jika ada TM...
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....
Satu pernyataan teorema Rice diberikan pada halaman 35 dari "Kompleksitas Komputasi: Pendekatan Modern" (Arora-Barak): Fungsi parsial dari {0,1}∗{0,1}∗\{0,1\}^* hingga {0,1}∗{0,1}∗\{0,1\}^* adalah fungsi yang tidak harus didefinisikan pada semua inputnya. Kita mengatakan bahwa TM MMM menghitung...
Pada 1950-an sejumlah metode untuk meminimalkan sirkuit untuk fungsi Boolean telah ditemukan. Apakah ada perluasan dari metode tersebut atau yang serupa untuk mengoptimalkan kompleksitas waktu atau ruang dari algoritma? Misalnya implementasi bubble sort sebagai input untuk algoritma seperti itu...
Untuk membuktikan bahwa 3-pewarnaan dapat dipilih, apakah cukup untuk mengatakan: Setiap node dalam grafik memiliki 3 warna yang memungkinkan Karena itu kita dapat menghitung semua kemungkinan dan kemudian memeriksa bahwa tidak ada dua sisi yang menghubungkan node dengan warna yang...
Biarkan string input diberikan sebagai . Kemudian jika NFA saat ini dalam keadaan r (dan telah membaca input hingga alfabet w i ) maka sebelum membaca simbol input berikutnya NFA terbagi menjadi dua NFA, satu berada di keadaan r dan yang lainnya di s , jika ada transisi dari tipe r ϵ → s . Jika ada...
Membaca pertanyaan ini, " Masalah RE yang tidak dapat dipastikan tetapi tidak menyelesaikan Turing ", bahasa berikut muncul di benak saya: Jika adalah fungsi berang-berang yang sibuk (skor maksimum yang dapat dicapai di antara semua penghentian 2-simbol n-state mesin Turing dari tipe yang...
Fungsi Boolean adalah fungsi .f: { 0 , 1 }n→ { 0 , 1 }f:{0,1}n→{0,1}f:\{0,1\}^n\rightarrow\{0,1\} Boolean basis dikenal sebagai Turing selesai karena memungkinkan urutan s ∈ { 0 , 1 } dibalik atau dibiarkan tidak berubah. Hal yang sama dapat dikatakan untuk gerbang X O R.( ∨ , ∧...
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...
Mengapa angka yang dapat dihitung (dalam arti Turing) dapat dihitung? Pasti sangat jelas, tetapi saya saat ini tidak
Dalam pertanyaan sebelumnya Apa sebenarnya algoritma itu? , Saya bertanya apakah memiliki "algoritma" yang mengembalikan nilai fungsi berdasarkan array nilai yang dihitung adalah algoritma. Salah satu jawaban yang menarik perhatian saya adalah yang ini: Contoh faktorial masuk ke model...