Membaca beberapa utas baru-baru ini tentang komputasi kuantum (di sini , di sini , dan di sini ), membuat saya ingat pertanyaan menarik tentang kekuatan beberapa jenis mesin pelestarian .ℓhalℓp\ell_p Bagi orang yang bekerja dalam teori kompleksitas menuju kompleksitas kuantum, teks pengantar yang...
Saya baru-baru ini berdiskusi tentang Mesin Turing ketika saya ditanya, "Apakah Mesin Turing berasal dari automata, atau sebaliknya?" Tentu saja saya tidak tahu jawabannya, tetapi saya ingin tahu. Mesin Turing pada dasarnya adalah versi yang sedikit lebih canggih dari Automata Push-Down. Dari itu...
Saya pernah membaca di suatu tempat bahwa mesin Turing tidak dapat menghitung ini dan karena itu tidak dapat diputuskan tetapi mengapa? Mengapa secara komputasi mustahil bagi mesin untuk menghasilkan pohon parse dan membuat keputusan? Mungkin saya salah dan itu bisa
Masalah keputusan CNF-SAT dapat digambarkan sebagai berikut: Input: Rumus boolean ϕϕ\phi dalam bentuk normal konjungtif. Pertanyaan: Apakah ada tugas variabel yang memenuhi ?ϕϕ\phi Saya sedang mempertimbangkan beberapa pendekatan berbeda untuk memecahkan CNF-SAT dengan mesin Turing dua-tape...
Seperti yang Anda tahu ada banyak anomali untuk mesin Turing tape tunggal ketika waktunya adalah : simulasi multi-tape TM, simulasi alfabet tape yang lebih besar hanya dengan { 0 , 1 , b } , konstruktivitas waktu, non-sesak teorema hierarki waktu, ...o(n2)o(n2)o(n^2){0,1,b}{0,1,b}\{0,1,b\} Juga...
Apakah mungkin untuk menguji secara algoritmik apakah bilangan yang dihitung rasional atau bilangan bulat? Dengan kata lain, apakah mungkin bagi perpustakaan yang mengimplementasikan angka yang dapat dihitung untuk menyediakan fungsi isIntegeratau isRational? Saya menduga itu tidak mungkin, dan...
Penafian: Saya tahu sedikit tentang teori kompleksitas. Maaf, tetapi benar-benar tidak ada cara untuk mengajukan pertanyaan ini tanpa (sangat) singkat: Apa yang seharusnya menjadi morfisme dalam kategori "the" dari mesin Turing? Ini jelas subyektif dan tergantung pada interpretasi seseorang...
Bahasa apa pun yang tidak lengkap Turing tidak dapat menulis penerjemah untuk itu sendiri. Saya tidak tahu di mana saya membaca itu tetapi saya telah melihatnya digunakan beberapa kali. Sepertinya ini memunculkan semacam bahasa "Turing" non-Turing lengkap; satu-satunya yang hanya bisaditafsirkan...
Salah satu hal menakjubkan tentang ilmu komputer adalah bahwa implementasi fisik dalam beberapa hal "tidak relevan". Orang-orang telah berhasil membangun komputer dari beberapa substrat yang berbeda - relay, tabung hampa udara, transistor diskrit, dll. Orang mungkin akan segera berhasil membangun...
Saya mencari jawaban pasti untuk pertanyaan judul. Apakah ada seperangkat aturan yang menerjemahkan program apa pun ke dalam konfigurasi potongan terbatas di papan infinite, sehingga jika hitam dan putih hanya memainkan gerakan hukum, permainan berakhir pada waktu terbatas jika program...
Dari sudut pandang matematika / komputasi murni abstrak, (bagaimana) seseorang dapat menemukan atau alasan tentang masalah seperti 3-SAT, Subset Sum, Travelling Salesman dll.,? Apakah kita bahkan dapat menalarinya dengan cara yang bermakna hanya dengan sudut pandang fungsional ? Apakah itu...
Diberi bahasa L yang didefinisikan oleh Turing Machine yang memutuskannya, apakah mungkin menentukan secara algoritmik apakah L terletak pada
Sehubungan dengan pertanyaan ini, terpikir oleh saya untuk bertanya-tanya: apa kompleksitas waktu untuk satu mesin single-head Turing untuk menghitung panjang inputnya? Untuk lebih spesifik, misalkan alfabet tape adalah , inputnya adalah string dalam ( 0 + 1 ) ∗ dikelilingi oleh blank, mesin...
Apakah ada bukti bahwa emulasi mesin Turing pada mesin Turing yang terlupa tidak dapat dilakukan dalam waktu kurang dari O(mlogm)O(mlogm)\mathcal{O}\left(m\log m\right) mana mmm adalah jumlah langkah yang digunakan mesin Turing? Atau ini hanya batas atas? Dalam makalah Paul Vitányi tentang...
Sederhananya: apa korespondensi antara mesin Turing dengan oracle, dan keluarga sirkuit seragam dengan oracle? Bagaimana yang terakhir didefinisikan untuk mendapatkan model komputasi yang sama, untuk mesin Turing oracle yang diberikan? Ini mungkin pertanyaan mendasar, tetapi tidak jelas ke mana...
Tentukan sebagai kelas bahasa yang dapat diterima oleh mesin Turing (multitape) dalam waktu f ( n ) + 1 . (" + 1 " hanya untuk menyederhanakan notasi dan menghindari kebingungan.) Perhatikan bahwa tidak ada O ( ⋅ ) di sekitar f ( n ) + 1 .DTIME(f(n))DTIME(f(n))\mathsf{DTIME}(f(n))f(n)+1f(n)+1f(n) +...
Masalah penghentian diketahui tidak dapat diperhitungkan. Namun, dimungkinkan untuk secara "kompres" informasi secara eksponensial tentang masalah penghentian, sehingga pengompresannya dapat dihitung. Lebih tepatnya, adalah mungkin untuk menghitung dari deskripsi mesin Turing dan saran bit...
Teorema hierarki waktu menyatakan bahwa mesin turing dapat memecahkan lebih banyak masalah jika mereka memiliki (cukup) lebih banyak waktu. Apakah itu tahan jika ruang terbatas asimptotik? Bagaimana DTISP(g(n),O(s(n)))DTISP(g(n),O(s(n)))\textrm{DTISP}(g(n), O(s(n))) terkait dengan...
Apakah ada Mesin Turing yang dapat memutuskan apakah hampir semua Mesin Turing lainnya berhenti? Misalkan kita memiliki beberapa enumerasi N→{Mi}N→{Mi}\mathbb{N} \rightarrow \{M_i\} dari mesin Turing, dan beberapa gagasan "ukuran" dari satu set bilangan alami ∥⋅∥‖⋅‖\| \cdot \| , dan kami...
Saya cukup yakin bahwa saya bukan yang pertama untuk menghibur gagasan bahwa saya akan hadir. Namun, akan sangat membantu jika saya dapat menemukan literatur yang terkait dengan ide tersebut. Idenya adalah untuk membangun Mesin Turing M dengan properti bahwa jika P = NP maka M akan menyelesaikan...